algorithm - 前缀到中缀转换算法附图

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 (say)

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

我在哪里做了不正确的假设？ 有人可以麻烦解释一下吗？

Answer 1

我不太明白你的问题。

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

如果您希望您的输出看起来像图表上那样，您需要您的堆栈为 * - A B C(注意每个元素之间的空格!)。

编辑:

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

OK，这样你就把第一个*存入了temp(a)，写了一个((b.i.)，调用了算法与剩余的堆栈(b.ii.)。这会抛出一个空白，然后您将 - 存储在下一个分支的 temp 中，写一个 (, 并用剩余的堆栈调用算法。在某个时候，你最终进入 d.ii.，你刚刚写了一个 A 输出，给你

((A

剩下的栈是

_B_C

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

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