1. 基本介绍

逆波兰表达式，英文为 Reverse Polish notation，跟波兰表达式（Polish notation）相对应。之所以叫波兰表达式和逆波兰表达式，是为了纪念波兰的数理科学家 Jan Łukasiewicz。其在著作中提到：我在1924年突然有了一个无需括号的表达方法，我在文章第一次使用了这种表示法。

平时我们习惯将表达式写成 (1 + 2) * (3 + 4)，加减乘除等运算符写在中间，因此称呼为中缀表达式。

而波兰表达式的写法为 ( * (+ 1 2) (+ 3 4))，将运算符写在前面，因而也称为前缀表达式。

逆波兰表达式的写法为 ((1 2 +) (3 4 +) * )，将运算符写在后面，因而也称为后缀表达式。

波兰表达式和逆波兰表达式有个好处，就算将圆括号去掉也没有歧义。上述的波兰表达式去掉圆括号，变为 * + 1 2 + 3 4。逆波兰表达式去掉圆括号，变成 1 2 + 3 4 + * 也是无歧义并可以计算的。事实上我们通常说的波兰表达式和逆波兰表达式就是去掉圆括号的。而中缀表达式，假如去掉圆括号，将 (1 + 2) * (3 + 4) 写成 1 + 2 * 3 + 4，就改变原来意思了。

下图是用表达式a*(b+c)-e/f构造的二叉树。

中序遍历，就是日常用的表达式写法。对于加法和减法需要加括号。

用前序遍历，对应前缀表达式：-*a+bc/ef

用后序遍历，对应后缀表达式：abc+*ef/-

那怎么构造这棵表达式的树呢？

  1. 中缀表达式，选最后运算的符号作为根结点，遍历左右两部分即可。
  2. 波兰表达式，用最前面的运算符号作为根结点，碰到数字就作为根节点即可。
  3. 逆波兰表达式，从底到上构造。

2. 编程

3. 作业

1、

【CSP 2020 提高组第一轮 q12】表达式 a*(b+c)-d 的后缀表达形式为（ ）。
A. abc*+d-   B. -+*abcd   C. abcd*+-   D. abc+*d-  

2、

【NOIP 2018 提高组初赛 q06】表达式 a * d - b * c 的前缀形式是（ ）。
A. a d * b c * -   B. - * a d * b c  
C. a * d - b * c   D. - * * a d b c  

3、

【NOIP 2017 提高组初赛 q07】表达式 a * (b + c) * d 的后缀形式是（ ）。
A. a b c d * + *   B. a b c + * d *  
C. a * b c + * d   D. b + c * a * d  

4、

【NOIP 2016 提高组初赛 q06】表达式 a*(b+c)-d 的后缀表达形式为（ ）。
A. abcd*+-   B. abc+*d-  
C. abc*+d-   D. -+*abcd  

5、

【NOIP 2010 提高组初赛 q07】前缀表达式“+ 3 * 2 + 5   12 ” 的值是（ ）。
A. 23   B. 25   C. 37   D. 65  

6、

【NOIP 2009 提高组初赛 q06】表达式a*(b+c)-d的后缀表达式是：
A. abcd*+-   B. abc+*d-  
C. abc*+d-   D. -+*abcd  

7、

【NOIP 2017 普及组初赛 q12】表达式 a * (b + c) * d 的后缀形式是（ ）。
A. a b c d * + *   B. a b c + * d *  
C. a * b c + * d   D. b + c * a * d  

8、

【NOIP 2010 普及组初赛 q09】前缀表达式+ 3 * 2 + 5 12的值是（ ）。
A. 23   B. 25   C. 37   D. 65  

9、

【NOIP 2009 普及组初赛 q13】表达式a*(b+c)-d的后缀表达式是：
A. abcd*+-   B. abc+*d-  
C. abc*+d-   D. -+*abcd