我正在尝试制作一个从后缀到中缀表示法的转换器,并且需要一些帮助。已经有关于中缀到后缀转换的问题 https://stackoverflow.com/questions/2431863/infix-to-postfix-and-unary-binary-operators,这给出了一个我无法转换回来的例子。 (注意:那里缺少一个减号!)
以下是我的转换器的输出,其中第一个“列”是后缀输入,第二个是我的中缀输出,第三个是我可能应该得到的(?):
2 - = - 2 =? - 2 true
1 + 2 + = + 1 + 2 =? + 1 + 2 true
1 + 2 + + = + (+ 1 + 2) =? + 1 + + 2 false
1 + 2 + + 3 - - 4 - - = - (- (+ (+ 1 + 2) - 3) - 4) =? + 1 + + 2 - - 3 - - 4 false
你认为这个问题有可能解决吗,或者最后两行实际上转换正确了?你会如何编写算法来解决这个问题?
请假设有更多的运营商(不仅+
and -
) 可以设置为一元和二元,其中一元运算符的优先级高于二元运算符。
参考
-
Ruby 测验 #148:后缀到中缀 http://www.rubyquiz.com/quiz148.html,也通过谷歌网上论坛 http://groups.google.com/group/comp.lang.ruby/browse_frm/thread/1fc1b43a91b6ceed
-
支持一元运算符的调车场算法(C、Python、Perl) http://en.literateprograms.org/Shunting_yard_algorithm_(Perl)关于识字计划
后缀表示法没有优先级的概念,因为任何运算符的操作数始终是堆栈上的前 N 个值(然后由运算符的结果替换)。
后缀表示法的一个问题是它不能很好地处理可以根据操作数数量引用不同运算符的运算符符号(例如 -,它可以表示一元或二进制减号)。解决这个问题的唯一方法是确保每个运算符都有一个唯一的符号来代表它。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)