日期:2014-05-18  浏览次数:20699 次

小女子还是不太理解前缀表达式转后缀表达式,求大神指点迷津。。
翻了很多资料,结果几乎都是C/C++的,之前也有大神指点过。
理论上好像有点明白了,真到写代码又不会了。。。
我知道前缀转后缀就是树的后序遍历。
能不能请大神们写点代码再次帮助我理解一下。。。。
灰常感谢各位。。。

------解决方案--------------------
学过编译原理里面的算符优先文法分析吗?
对于(a - b) / c这个式子
首先需要建立一个优先级的表:类似于 / > -这样的。
记住一点,读入的为操作数时,直接放入操作数栈,读入符号时,要和符号栈顶部的符号做优先级比较。
操作数栈:
符号栈:# //开始为#,设定#的优先级小于任何符号
考察第一个字符:( 由于( > #,读入
操作数栈:
符号栈:#(
第二个:a 直接读入
操作数栈:a
符号栈:#(
第三个:- 这儿你要明白-是大于(的,左括号的优先级应该大于#
操作数栈:a
符号栈:#( -
第四个:b 直接读入
操作数栈:a b
符号栈:#( -
第五个:) 这里想想也会明白,右括号的优先级应该是大于任何符号的,由于)> -,说明要运算了
操作数栈:a b
符号栈:#( -
因此输出后缀式的第一部分:a b -,在输出之后,栈变为:
操作数栈:a-b的结果
符号栈: # (
这时,由于)并未读入,所以还要再考察)和符号栈的栈顶符号,
这里会用到一个默认设定,就是左括号遇到右括号的时候,两个都放弃。栈变为:
操作数栈: a-b的结果
符号栈:# 
之后的步骤就是重复的了,这个很好理解,
如果你理解到了,但是不会写代码的话,
说明你擅长用你学到的语言来把这个问题转化为计算机可以实现的代码!

------解决方案--------------------
探讨

额。。。貌似我才自学一个月,接触的语言也只有C#。。。
至于书籍,选的是《数据结构与算法C#语言版》,外加传智播客.net的入门视频
楼上的意思是不是要设一个优先级,(为最先,然后/*-+,然后读到)的时候把这些符号压入另一个栈里面么,那数栈如何读取呢?

PS,我只是想设计一个类,在类里面实现一个字符串类似于“- + a b c”的前缀表达式转成"a b + c -"的后缀表达式