带数字的前缀转换算法的前缀 [英] Prefix to Infix Conversion Algorithm with figure

问题描述

经过Google搜索后，我发现了它！

After some google search I find it!

前缀前缀

此算法是一种非尾递归方法。
反转的输入字符串完全推入堆栈中。

This algorithm is a non-tail recursive method. The reversed input string is completely pushed into a stack.

prefixToInfix(stack)
   1) IF stack is not empty
     a. Temp -->pop the stack
     b. IF temp is a operator
       i. Write a opening parenthesis to output
       ii. prefixToInfix(stack)
       iii. Write temp to output
       iv. prefixToInfix(stack)
       v. Write a closing parenthesis to output
    c. ELSE IF temp is a space -->prefixToInfix(stack)
    d. ELSE
       i. Write temp to output
       ii. IF stack.top NOT EQUAL to space -->prefixToInfix(stack)

当栈顶为

F（ABC）

F(ABC)

我们输入算法，因为当前值为

and we enter the algorithm, "A" is written to the output as it was currently the value of

temp = A（例如），所以将 A写入输出p>

temp=A (say)

现在我如何在输出列上得到'-'，根据算法，下一个临时值将是在最后一次递归调用之后从堆栈中弹出的 B。
该图如何显示输出（（（A- ...

Now how I get '-' on the output column as according to the algorithm the next temp value will be "B" which was popped from the stack after the last recursive call. How the diagram is showing output "((A-" ...

我在做不正确的假设的地方吗？
有人可以

Where I am doing the incorrect assumption ? Could someone take the trouble in explaining it ?

推荐答案

我不太理解您的问题。

如果您的堆栈为 ABC ，则 F（ABC）弹出A，进入分支di并写A输出到d.ii.并执行 F（BC），最后将B和C都写到输出。

If your stack is ABC, F(ABC) pops the A, goes into branch d.i. and writes an A to output, goes on into d.ii. and performs F(BC), which will, in the end, write both the B and C to output.

如果您希望输出看起来像图中的样子，则需要将堆栈设为 *-ABC （注意每个元素之间的空格！）。

If you want your output to look like it does on the diagram, you'll need your stack to be * - A B C (note the spaces between every element!).

（顺便说一句：所有这些步骤比描述的要容易，所以我建议您将算法作为程序编写，并在选择的调试器中启动它。）

(As an aside: all this is easier stepped through than described, so I suggest you write the algorithm as a program and start it in your choice of debugger.)

确定，因此您已经存储了第一个 * 在 temp （a）中，写为（（ bi）， d用剩下的堆栈调用该算法（b.ii.）。这会丢掉一个空格，然后将-存储在下一个分支的 temp 中，并写一个（，并用剩余的堆栈调用该算法。有时，您会在d.ii中结束。您刚刚写了一个A来输出，给您

OK, so you have stored the first * in temp (a), written a ( (b.i.), and called the algorithm with the remaining stack (b.ii.). This throws away a blank, then you store a - in the next branch's temp, write a (, and called the algorithm with the remaining stack. At some point, you end up in d.ii., you have just written an A to output, giving you

((A

其余堆栈为

_B_C

在顶部有一个空格，在B和C之间有另一个空格。

现在，d.ii。找到了该空格，不再执行任何操作：此控制分支已完成，然后回到我们的来源，即d.ii.在您的-控制分支中，您编写了-以在d.iii。输出，在d.iv.调用具有其余堆栈（ _B_C ）的算法，然后编写 B ，）， * 和 C 和最后一个）。

with a space on top and another space between B and C.
So now d.ii. finds the space and doesn't do anything anymore: this control branch is done, and we go back to where we came from, which was d.ii. in your - control branch. You write the - to output at d.iii., call the algorithm with the remaining stack (_B_C) at d.iv., and there you go, writing the B, a ), the * and C and the last ).

只记得您来自哪里，所以您知道要去哪里p完成当前递归操作后返回。

Just remember where you came from, so you know where to jump back after your current recursion is done.

这篇关于带数字的前缀转换算法的前缀的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！