逆波兰表达式

逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

中缀表达式5 + ((1 + 2) * 4) - 3写作

5 1 2 + 4 * + 3 -

下表给出了该逆波兰表达式从左至右求值的过程,堆栈栏给出了中间值,用于跟踪算法。

输入操作堆栈注释
5入栈5
1入栈5, 1
2入栈5, 1, 2
+加法运算5, 31, 2出栈,将结果3入栈
4入栈5, 3, 4
*乘法运算5, 123, 4出栈,将结果12入栈
+加法运算175, 12出栈,将结果17入栈
3入栈17, 3
-减法运算1417, 3出栈,将结果14入栈

计算完成时,栈内只有一个操作数,这就是表达式的结果:14

上述运算可以重写为如下运算链方法(用于HP的逆波兰计算器):[3]

1 2 + 4 * 5 + 3 -

wikipedia - 逆波兰表达式