带图的前缀到中缀转换算法

Question

---

经过一些谷歌搜索后我找到了它！

前缀到中缀

该算法是一种非尾递归方法。 反转的输入字符串被完全压入堆栈。

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)

，我们输入算法，“A”被写入输出，因为它当前的值

temp=A（比如说）

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

我在哪里做了错误的假设？ 有人能麻烦解释一下吗？

Answer 1

我不太明白你的问题。

如果您的堆栈是 ABC，F(ABC) 会弹出 A，进入分支 di 并将 A 写入输出，然后进入 d.ii。并执行F(BC)，最终将B和C写入输出。

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

编辑：（

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

好的，所以您已经存储了第一个 * 在 temp (a) 中，编写了一个 ( (bi)，并使用剩余的堆栈调用该算法 (b.ii.)。这会丢弃一个空白，然后你将一个 - 存储在下一个分支的 temp 中，编写一个 (，并使用剩余的堆栈调用该算法。在某个时刻，你最终在 d.ii. 中，您刚刚编写了一个 A 来输出，

((A

剩下的堆栈

_B_C

顶部有一个空格，B 和 C 之间有另一个空格。
所以现在 d.ii。找到空间并且不再做任何事情：这个控制分支完成了，我们回到我们来的地方，即 d.ii。在您的 - 控制分支中。您在 d.iii. 处编写要输出的 -，在 d.iv. 处使用剩余堆栈 (_B_C) 调用算法，然后就可以编写 < code>B、a )、* 和 C 以及最后一个 )。

只要记住你来自哪里，这样你就知道在当前的递归完成后跳回哪里。