2

替代文字

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

前缀到中缀

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

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”被写入输出，因为它是当前的值

温度=A（比方说）

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

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

4

1 回答 1

1

我不太明白你的问题。

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

如果您希望您的输出看起来像它在图表上的样子，您将需要您的堆栈* - A B C（注意每个元素之间的空格！）。

编辑：

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

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

((A

剩下的堆栈是 

_B_C

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

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

于 2010-12-07T08:11:01.397 回答