波兰表示法与逆波兰表示法

算术形式

表达“三与四相加”时，前缀记法（即波兰表达式）写作 +34，中缀记法写作 3+4，后缀记法（即逆波兰表达式）写作 34+。中缀表达式 (1-2)*3 的前缀记法为 *-123，后缀记法为 12-3*。

请注意，逆波兰表达式不是把波兰表达式反转。

运算波兰表达式时，无需记住运算的层次，只需要直接寻找第一个运算的操作符。以二元运算为例，从左至右读入表达式，遇到一个操作符后跟随两个操作数时，则计算之，然后将结果作为操作数替换这个操作符和两个操作数；重复此步骤，直至所有操作符处理完毕。

逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是：操作数入栈；遇到操作符时，操作数出栈，求值，将结果入栈；当一遍后，栈顶就是表达式的值。

由于简单运算符都是二元的，所以波兰表达式与逆波兰表达式不需要括号。

1
2
3
4
5
  - / * + 5 7 3 6 4
= - / * 12    3 6 4
= - / 36        6 4
= - 6             4
= 2

1
2
3
4
  + - 6 * 4 5 2
= + - 6 20    2
= + -14       2
= -12

1
2
3
4
5
  5 7 + 3 * 6 / 4 -
= 12    3 * 6 / 4 -
= 36        6 / 4 -
= 6             4 -
= 2

1
2
3
4
  6 4 5 * - 2 +
= 6 20    - 2 +
= -14       2 +
= -12