17.2.6 后缀表达式
后缀表达式也叫逆波兰式，是中间代码的一种常见表示。它把运算符写在操作数之后，因此不需要括号也能表达运算顺序，特别适合用栈求值。
三种表达式形式
| 形式 | 写法 | 遍历视角 |
|---|---|---|
| 前缀表达式 | +AB | 根-左-右 |
| 中缀表达式 | A+B | 左-根-右 |
| 后缀表达式 | AB+ | 左-右-根 |
普通数学表达式多为中缀形式，但中缀形式依赖括号和优先级。编译器把表达式转成树后，括号不再需要，因为树的结构已经固定了运算顺序。
表达式树
以 (A-B)*(C+5) 为例，最后执行的是乘法，所以乘号是整棵树的根；左子树是 A-B，右子树是 C+5。
mermaid
flowchart TB
M["*"] --> S["-"]
M --> P["+"]
S --> A["A"]
S --> B["B"]
P --> C["C"]
P --> N["5"]对这棵树做后序遍历：左子树 AB-，右子树 C5+，最后根 *，得到：
text
AB-C5+*用栈求值
后缀表达式从左到右扫描。
| 读到 | 操作 |
|---|---|
| 操作数 | 入栈 |
| 运算符 | 弹出所需操作数，计算后结果入栈 |
注意减法、除法这类非交换运算的顺序。后弹出的通常是左操作数，先弹出的通常是右操作数。
例如后缀表达式 AB-：
- 读
A，入栈。 - 读
B，入栈。 - 读
-，弹出B和A，计算A-B。
中缀转后缀的考试方法
如果题目给语法树，直接做后序遍历，最稳。如果题目给中缀表达式，先按括号和优先级画出表达式树，再后序遍历。不要凭感觉从左到右移动符号，复杂表达式很容易把根节点放错。
| 表达式 | 表达式树根 | 后缀表达式 |
|---|---|---|
A+B | + | AB+ |
(A-B)*(C+5) | * | AB-C5+* |
X*(5+Y)-A/B | - | X5Y+*AB/- |
为什么后缀表达式适合编译器
后缀表达式是一种线性表示，消除了括号和优先级规则，机器可以用栈顺序处理。相比源表达式，它更接近执行过程；相比目标机器代码，它仍然与具体机器保持一定距离，所以适合作为中间表示。
小练习
题：表达式 (A+B)*C 的后缀表达式是什么？
答：AB+C*。先算 A+B，再与 C 相乘。
自查
- 后缀表达式为什么不需要括号？
- 从表达式树求后缀表达式时为什么是后序遍历？
- 用栈计算
AB-时，为什么不能算成B-A？