后缀与一元/二元运算符中缀 [英] Postfix to infix with unary/binary operators
问题描述
我试图做一个转换器从后缀中缀表示法,需要一些帮助。已经有关于缀 - 后缀转换,其中的问题给我未能转换回一个例子。 (注:一个减号缺少有)
以下是我的转换器,其中,第1塔是后缀输入的输出,第二个是我的缀输出,并且第三是我大概应该得到(?):
2 - = - 2 =? - 2真
1 + 2 + = + 1 + 2 =? + 1 + 2真
1 + 2 + + + =(+ 1 + 2)=? + 1 + 2假
1 + 2 + 3 - - 4 - - = - ( - (+(+ 1 + 2) - 3) - 4)=? + 1 + 2 - - 3 - - 4虚假
你认为是可能的解决这个问题,还是最后两行实际上是正确转换?你会怎么写算法来解决这个问题呢?
请,假设更多的运营商(不仅 +
和 -
)可以被设置为两个一元和二元,其中一元运算符比二进制的更高的优先级。
参考
后缀表示法不具备优先的概念,作为操作数为任何操作者总是堆栈顶部的N个值(其然后由操作者的结果取代。
一个问题后缀符号是,它不与该可指根据操作数的数目不同的运营商运营的符号应付以及(如 - ,其可以表示任一元或二元减号)。出来的,唯一的办法是确保每个运营商都有代表它的独特象征。
I am trying to make a converter from postfix to infix notation and need some help. There is already a question about infix-to-postfix conversion, which gives an example I am failing to convert back. (Note: a minus sign is missing there!)
The following is the output of my converter, where the 1st "column" is postfix input, the 2nd is my infix output, and the 3rd is what I probably should get(?):
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
Do you think that it is possible to solve this problem, or the last two lines are actually converted correctly? How would you write algorithm to solve this problem?
Please, assume that more operators (not only +
and -
) can be set as both unary and binary, where unary operators have higher precedence than binary ones.
References
- Ruby Quiz #148: Postfix to Infix, also via Google Groups
- Shunting-yard algorithm (C, Python, Perl) with unary operator support on LiteratePrograms
Postfix notation does not have the concept of precedence, as the operands for any operator are always the top N values on the stack (which are then replaced by the result of the operator.
One problem with postfix notation is that it does not cope well with operator symbols that can refer to different operators depending on the number of operands (such as -, which can denote either unary or binary minus). The only way out of that is to ensure each operator has a unique symbol representing it.
这篇关于后缀与一元/二元运算符中缀的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!