栈的应用前缀中缀后缀

p19（13.1 分钟）、p20（13.6 分钟）、p21（17.6 分钟）

基本概念#

术语#

1
表达式由常量、变量、运算符、括号组成
2
操作数 = 被运算的对象/值
3
运算符 = 运算符或括号

这里只讨论二元运算符（恰好需要两个操作数的运算符）；操作数本身也可以是表达式。

三种记法#

1
中缀 infix    运算符在两个操作数中间   最常见的写法
2
前缀 prefix   运算符在操作数之前       波兰式 Polish notation，1924 年由一位波兰逻辑学家提出
3
后缀 postfix  运算符在操作数之后       逆波兰式 Reverse Polish，20 世纪 50 年代由计算机科学家提出

关键性质：前缀/后缀中一个操作数只能与一个运算符关联，因此没有歧义，解析求值不需要优先级和结合性规则，也不需要括号。

后缀最易解析、时间和内存成本最低，所以机器运算更偏好它。

存储形式：以字符串保存时用空格或逗号等分隔符区分操作数与运算符。

优先级与结合性#

1
1（最高）   括号 ( )         —
2
2           指数 ^           右结合（从右往左）
3
3           乘法 *、除法 /    左结合（从左往右）
4
4           加法 +、减法 -    左结合（从左往右）

同一优先级之间的冲突由「结合性（associativity）」解决：从左到右 = 左结合；从右到左 = 右结合。

判定步骤：先看优先级，再看结合性。

手算例子#

1
4 + 6 * 2      先乘后加 = 16      先加得 20（错）
2
2^3^2          右结合 = 512       先算左边 = 64（错）
3
只含加减、同级左结合   3          先做加法得 1（错）

4 + 6 * 2 想先加就必须写成 (4 + 6) * 2，因为括号优先级最高。

三种记法的互相改写#

1
2 + 3      →  前缀 + 2 3         后缀 2 3 +
2
P - Q      →  前缀 - P Q         后缀 P Q -
3
A + B * C  →  前缀 + A * B C     后缀 A B C * +

手动转换方法（通用）：按优先级从最内层开始一步步转换，中间步骤可加括号，全部完成后再去掉所有括号。

括号提高人类可读性，但对机器而言去掉括号反而省下存储括号信息的内存；中缀最利于人，前缀/后缀最利于机器。

后缀求值#

手算规则#

1
从左往右扫描，找「第一个出现的运算符」
2
运算符的操作数总在它左侧
3
即找首次出现的「操作数 操作数 运算符」模式
4
用它作用于紧邻的前两个操作数并化简表达式
5
重复到所有运算符处理完

例：中缀 2*3 + 5*4 - 9

1
后缀串：2 3 * 5 4 * + 9 -
2
手算：先算 2*3 = 6
3
      再算 5*4 = 20
4
      再算 6+20 = 26
5
      最后 26-9 = 17
6
最终答案 17

算法#

1
创建栈 S
2
循环 for i = 0 到 len-1，X[i] 是操作数或运算符：
3
    是操作数 → push 入栈
4
    是运算符 → 连续 pop 两次，把操作数的值存入变量（op1、op2）
5
              执行运算，结果再 push 回栈
6
扫描结束，栈中只剩一个元素 = 最终结果，返回栈顶

弹出顺序#

后缀：第一次 pop 得到的是第二个操作数 op2（右操作数），第二次 pop 才是 op1（左操作数）。

这个顺序对加法和乘法无所谓，但对减法和除法很重要——5 3 - 得是 5−3，弹反了就成了 3−5。

效率#

只需在表达式字符串上扫一遍，是高效算法。

为什么能用栈：每次从同一侧插入操作数、又从同一侧取出，最后进来的最先出去 → LIFO。

前缀求值#

扫描方向：从右往左。规则：是操作数 → push；是运算符 → pop 两个元素。

弹出顺序和后缀相反#

1
前缀：第一次弹出的元素是第一个操作数（左）
2
      第二次弹出的是第二个操作数（右）

这个顺序对加法和乘法无所谓，但对减法和除法很重要。

完整演算（与后缀同一个表达式）#

1
从右往左读：9、4、5
2
  遇 *  → 弹 5（op1）、弹 4（op2）→ 5*4 = 20 入栈
3
读 2、3
4
  遇 *  → 3*2 = 6 入栈
5
遇 +    → 弹出 20 和 6 → 26 入栈
6
遇 -    → 弹出 26 和 9 → 26-9 = 17 入栈
7
答案 17

前缀求值还有别的做法，但这种最简单最直接。

中缀转后缀#

先看低效做法#

按优先级手动逐步转换（先 B*C → BC*，再处理加法，最后去括号）——也能在程序里运用这种逻辑，但效率不高、实现复杂。

两条关键观察#

1
① 从中缀到后缀，操作数自左向右出现的相对顺序不变
2
② 运算符的顺序可能改变，而在后缀中运算符总是按它们应当被执行的顺序排列

算法（从左到右单次扫描，直接产出后缀）#

1
① 操作数 → 直接追加到输出的后缀字符串
2
② 运算符 → 它自己不能立刻输出（还没见到右操作数）
3
            先把栈中优先级更高的运算符弹出并追加
4
            然后把这个运算符压栈
5
③ 循环结束后，把栈里剩余的运算符全部弹出并追加
6
④ 返回结果字符串

口头规则：栈中任何比我们正在查看的运算符具有更高优先级的运算符都可以弹出并放入后缀表达式。

但演算时同级的 + 也被弹了出去，理由是加法和减法优先级相同，但左边先出现的会被优先考虑（左结合）。

所以实操上等价于：

1
左结合运算符  →  栈顶优先级 ≥ 当前运算符就弹出
2
右结合运算符  →  改为「严格大于」才弹出

「右结合用 >」这一点没有讲明，是从优先级表推导出来的。

为什么要压栈：不确定是否已处理完它的右操作数；一旦遇到优先级更低的运算符，就标志着右操作数的边界。

伪代码骨架#

1
infixToPostfix(X):
2
    S = 空栈
3
    res = ""
4
    for i in 0..len-1:
5
        if X[i] 是操作数:
6
            res += X[i]
7
        else:                                  /* 运算符 */
8
            while (!S.empty() && S.top() 优先级更高):
9
                res += S.pop()
10
            S.push(X[i])
11
    while (!S.empty()):
12
        res += S.pop()
13
    return res

加括号后的额外规则#

括号内的表达式应视为独立完整的表达式，括号外的运算符不影响其执行；嵌套括号先处理内层。

标记类型变为四种：操作数、运算符、左括号、右括号。

1
① 遇到左括号 → 直接压栈
2

3
② 遇到右括号 → 一直弹出并追加，直到遇到左括号
4
               然后还要把那个左括号也弹掉
5
               （「针对这个括号，我们已经完成操作」）
6

7
③ 运算符规则的变化 → 弹出时「仅弹出直到遇到左括号为止」
8
                    因为左括号是「最后一个打开的括号的边界」
9
                    所以 while 条件里要多加一个「栈顶不是左括号」的判断

判断括号要用通用函数 isOpening / isClosing，因为还可能是 {、[，不能只写 == '('。

演算例子#

例 1（含两层括号）：后缀为 A B + C * D E * -

例 2：中缀 A * (B + C)

1
A 是操作数 → 追加
2
* 直接进栈（栈空，无可比较）
3
遇左括号 → 直接进栈
4
B 追加
5
+ 时栈顶是左括号，不能往下查看，只能压入
6
C 追加
7
遇右括号 → 一直弹出到左括号，并把左括号也弹出
8
到表达式末尾 → 栈中剩余全部弹出
9

10
最终后缀：A B C + *

三种记法对比#

	中缀	前缀	后缀
运算符位置	中间	前	后
别名	—	波兰式	逆波兰式
需要括号吗	需要	不需要	不需要
需要优先级吗	需要	不需要	不需要
求值扫描方向	—	从右往左	从左往右
第一次 pop 是	—	op1（左）	op2（右）
谁更喜欢	人	机器	机器（最优）

坑#

优先级表：括号最高，指数其次，乘除再次，加减最低；指数是右结合，其余左结合。
2^3^2 = 512，不是 64。
后缀求值先弹右（op2）后弹左（op1）；前缀求值从右往左扫，先弹左（op1）后弹右（op2）。两者相反，最容易记混。
中缀转后缀时，同级运算符也要弹（左结合），等价于「栈顶 ≥ 当前就弹」。
右括号要把左括号也弹掉；运算符的 while 循环还要加「栈顶不是左括号」的条件，否则会把括号内的运算符全弹出去。