带图的前缀到中缀转换算法
经过一些谷歌搜索后我找到了它！
前缀到中缀
该算法是一种非尾递归方法。 反转的输入字符串被完全压入堆栈。
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-”...
我在哪里做了错误的假设？ 有人能麻烦解释一下吗？
After some google search I find it!
Prefix to Infix
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)
when the Stack top is
F(ABC)
and we enter the algorithm, "A" is written to the output as it was currently the value of
temp=A (say)
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 ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我不太明白你的问题。
如果您的堆栈是
ABC，F(ABC)会弹出 A，进入分支 di 并将 A 写入输出，然后进入 d.ii。并执行F(BC)，最终将B和C写入输出。如果您希望输出看起来像图表中的那样，则需要堆栈为
* - AB C（注意每个元素之间的空格！）。编辑：（
顺便说一句：所有这些都比描述的更容易逐步完成，所以我建议您将算法编写为程序并在您选择的调试器中启动它。）
好的，所以您已经存储了第一个
* 在temp(a) 中，编写了一个((bi)，并使用剩余的堆栈调用该算法 (b.ii.)。这会丢弃一个空白，然后你将一个-存储在下一个分支的temp中，编写一个(，并使用剩余的堆栈调用该算法。在某个时刻，你最终在 d.ii. 中，您刚刚编写了一个 A 来输出，剩下的堆栈
顶部有一个空格，B 和 C 之间有另一个空格。
所以现在 d.ii。找到空间并且不再做任何事情：这个控制分支完成了，我们回到我们来的地方，即 d.ii。在您的
-控制分支中。您在 d.iii. 处编写要输出的-，在 d.iv. 处使用剩余堆栈 (_B_C) 调用算法，然后就可以编写 < code>B、a)、*和C以及最后一个)。只要记住你来自哪里，这样你就知道在当前的递归完成后跳回哪里。
I don't quite understand your question.
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 performsF(BC), which will, in the end, write both the B and C to output.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!).Edit:
(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.)
OK, so you have stored the first
*intemp(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'stemp, 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 youand the remaining stack is
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 theB, a), the*andCand the last).Just remember where you came from, so you know where to jump back after your current recursion is done.