表达式求值与三种表示法 · 学习笔记
日期：2026-09-17 主题：中缀 / 前缀 / 后缀表达式、栈求值、相互转换
配套练习：9 道转换题已全部完成并批改（错题记录见第 7 节）
1. 三种表达式是什么
同一个算式有三种"拼写方式"，以 (1 + 2) * 3 为例：
| 名称 | 别名 | 运算符位置 | 写法 | 靠什么消除歧义 |
|---|---|---|---|---|
| 中缀 | 常规写法 | 两操作数中间 | (1 + 2) * 3 | 优先级规则 + 括号 |
| 前缀 | 波兰式 | 操作数前面 | * + 1 2 3 | 位置自解释，永不歧义 |
| 后缀 | 逆波兰式（RPN） | 操作数后面 | 1 2 + 3 * | 位置自解释，永不歧义 |
核心结论：
- 中缀给人看最直观，但机器必须懂优先级和括号才能解析；
- 前 / 后缀不需要括号、不需要优先级表，用栈一遍扫描就能算；
- 所以编译器、计算器通常把中缀转成后缀再求值——它是"人的写法"和"机器执行"之间的桥。
- 实际应用：编译器 / 解释器的表达式中间形式、栈式虚拟机（JVM 字节码本质是栈式求值）、Forth / PostScript 等栈式语言。
2. 表达式树：三种写法的统一图景
三种表达式是同一棵表达式树的三种遍历。以 a * b + c / d 为例：
+ ← 根 = 最外层（最后执行）的运算
/ \
× ÷
/ \ / \
a b c d
- 前缀 = 每棵子树根左右（运算符先写）→
+ × a b ÷ c d - 中缀 = 左根右（运算符夹中间，需优先级救场）→
a * b + c / d - 后缀 = 左右根（运算符最后写）→
a b × c d ÷ +
记住两条铁律：
- 后缀里每个运算符都在自己整棵子树的最末；前缀里则在最前。
- 最外层的运算符：前缀里排第一，后缀里排最后。
⚠️ 注意：把后缀整串倒抄 ≠ 前缀。a b × c d ÷ + 倒抄得 + ÷ d c × b a，每一对操作数左右互换了，不是合法前缀。倒读只能帮你找"根在哪"，不能当转换公式。
3. 用栈求值
3.1 后缀：从左往右扫
遇数字压栈；遇运算符弹出两个数计算，结果压回。
例：5 1 2 + 4 * + 3 -（即 5 + (1+2)*4 - 3）
扫描 5 栈: [5]
扫描 1 栈: [5, 1]
扫描 2 栈: [5, 1, 2]
扫描 + 1+2=3 栈: [5, 3]
扫描 4 栈: [5, 3, 4]
扫描 * 3*4=12 栈: [5, 12]
扫描 + 5+12=17 栈: [17]
扫描 3 栈: [17, 3]
扫描 - 17-3=14 栈: [14] ← 结尾栈里剩的唯一元素就是答案
⚠️ 减法、除法注意：先弹出的是右操作数。6 2 / 是先弹 2（右）、再弹 6（左），算 6÷2，不是 2÷6。
3.2 前缀：从右往左扫
为什么不能从左往右？因为运算符的操作数在它右边还没读到——扫到 * 时栈是空的，没东西可弹（后缀的规则直接失效）。
从右往左扫，任何运算符的右侧部分已全部进栈，规则成立：
* + 1 2 3 （即 (1+2)*3）
扫描 3 栈: [3]
扫描 2 栈: [3, 2]
扫描 1 栈: [3, 2, 1]
扫描 + 1+2=3 栈: [3, 3]
扫描 * 3*3=9 栈: [9]
⚠️ 与后缀相反：先弹出的是左操作数。- 5 3 从右往左扫到 - 时先弹 5（左）、再弹 3（右），算 5−3。
4. 相互转换：定根法（纸上标准流程）
4.1 中缀 → 前缀 / 后缀
- 标执行顺序号：给每个运算符标上它第几个被计算（括号优先、乘除高于加减、同级从左往右）；
- 序号最大的运算符是根；
- 根把式子切成左右两半，对每一半递归做同样的事；
- 落地：前缀按"根左右"，后缀按"左右根"。
实战示例：(a + b) * c - (d - e) / f
标序号： (a+b)① ×② (d−e)①' ÷②' 顶层 −③
↑ 序号最大 → 根是减号
切两半： 左 = (a+b)*c 右 = (d−e)/f
递归： 左根 ×，右根 ÷
落地前缀：- × + a b c ÷ - d e f
落地后缀：a b + c × d e - f ÷ -
⚠️ 经典错误（第 7 题踩过）：把根当成 ÷，做成 [(a+b)*c − (d−e)] ÷ f。在 X − Y / f 里，/ 只管 Y，不管左边全家。找根前先用序号法确认，别凭感觉。
4.2 后缀 / 前缀 → 中缀（栈拼接法）
遇"数"就压一个表达式；遇运算符弹出两个表达式拼成 (左 op 右) 再压回。最后栈里剩一个完整中缀式。
例：a b c * + d e * /
b、c 入栈 → 遇 * 拼 (b*c) → 与 a 拼遇 + 得 (a+(b*c))
d、e 入栈 → 遇 * 拼 (d*e) → 遇 / 得 ((a+b*c)/(d*e))
补括号规则（只补必要的）：
- 左孩子优先级 低于 父 → 补；同级 → 不补（左结合）；
- 右孩子优先级 低于或等于 父 → 补；只有严格更高才不补。
例：a b c - - 拼出根 -、右孩子 (b-c)，同级且父左结合 → 必须写 a - (b - c)。
4.3 前缀 ↔ 后缀直转
没有一步直达公式，走中间：后缀 → 树（或中缀）→ 前缀。
5. 易错点清单（按今日实战整理）
- 运算符抢跑：后缀里把
+写在a后面（a + b c * d -）、×写在两块中间（a b + × c d -）。→ 铁律：运算符等两个操作数都完整后才能出场，位置在整棵子树最后。 - 同级结合方向：
+ - × ÷全部左结合。a - b - c + d = (((a−b)−c)+d)，a / b / c = (a/b)/c。树往左长，别写成右结合。 - 根找错（优先级误读）：
X − Y / f的根是−不是÷。序号最大的运算符才是根。 - 括号强制优先：
a − (b + c) * d里括号内的+反而先算，转换时别让*抢跑。 - 多位数 / 负数：
12按字符拆会变成1和2；负号-3的-会被误当减法。→ token 之间必须加空格，程序里先把整体能解析成数字的串当操作数。 - 书写习惯：token 之间留空格（
a b + c d - *），单字母时省事，多位数时保命。
6. 自查三件套（每题必做）
- 代入对账：给变量代随机数（如 5, 3, 2, 1），中缀直接算一遍、后缀栈扫一遍、前缀从右往左扫一遍，三个结果相等才算过。负数、除法不顺眼的结果也要信计算（第 9 题答案是 −7，负号恰恰说明算对了）。
- 后缀合法性扫描：数一下栈里元素个数 n——遇数字 n+1；遇运算符要求 n≥2，然后 n−1。任何时刻 n≥1（出现 0 即"操作数不够"），扫描结束 n=1。前缀从右往左同理。
- 树核对：把画好的树按左右根（或根左右）走一遍，和写出的串对照。
7. 今日练习与错题记录
练习：9 道中缀题，每题写前缀 + 后缀。
| # | 中缀 | 后缀 | 前缀 |
|---|---|---|---|
| 1 | a + b * c - d | a b c * + d - | - + a * b c d |
| 2 | (a + b) * (c - d) | a b + c d - * | * + a b - c d |
| 3 | a - b - c + d | a b - c - d + | + - - a b c d |
| 4 | a * (b + c) - d / e | a b c + * d e / - | - * a + b c / d e |
| 5 | a - (b + c) * d | a b c + d * - | - a * + b c d |
| 6 | a / b / c | a b / c / | / / a b c |
| 7 | (a + b) * c - (d - e) / f | a b + c * d e - f / - | - * + a b c / - d e f |
| 8 | a * b + c * d - e * f | a b * c d * + e f * - | - + * a b * c d * e f |
| 9 | (3 + 4) * (2 - 6 / 2) | 3 4 + 2 6 2 / - * | * + 3 4 - 2 / 6 2 值 = −7 |
错题本（建议隔天重做这三题）：
- 第 1 题后缀：写成
a + b c * d -，+抢跑 → 复习 4.1 铁律； - 第 2 题后缀：
×写在c d前 → 同上； - 第 7 题：树根画成
÷（÷ 篡位），实际根是顶层−→ 复习 4.1 序号法。
错误线索回顾：第 1、2 题是"遍历顺序"病（用画树 + 左右根治好），第 7 题是"读优先级"病（用执行序号定根治好），第 8、9 题已全对 = 两条病根都清了。
8. 下一步
- 代码实现后缀求值（LeetCode 150「逆波兰表达式求值」）：栈的入门经典。注意整除向零截断（
6 / -132 = 0），先弹的是右操作数。 - 调度场算法（Shunting-yard）：编译器真正用的中缀→后缀算法，一遍扫描、不画树。核心是"运算符栈 + 优先级比较"。
- 进阶：LeetCode 224 / 227「基本计算器」。
方法论一句话总结：定根 → 切两半 → 递归 → 按根左右 / 左右根落地 → 代入 + 栈扫自查。