为什么用栈#

括号的嵌套规则要求最后出现的左括号最先被匹配，与栈的 LIFO 特性完全一致。

算法流程#

1. 初始化空栈
2. 从左到右扫描表达式
3. 遇左括号 (、[、{：入栈
4. 遇右括号 )、]、}：若栈空则失败（右括号多余），否则弹栈配对检查
5. 扫描结束后栈为空则成功，否则失败（左括号多余）

三种失败情况（⭐常考）#

复杂度#

三种表达式对比#

后缀表达式不需要括号，运算顺序由运算符出现的先后唯一确定。

中缀转后缀#

使用运算符栈，按优先级规则决定何时弹出：

1. 操作数 → 直接输出
2. ( → 入栈
3. ) → 弹出栈顶直到 (，( 弹出不输出
4. 运算符 → 弹出栈中优先级 ≥ 当前运算符的运算符，再入栈
5. 结束 → 弹出栈中剩余运算符

运算符优先级：

⚠️ 易错：左括号 ( 栈外优先级最高（保证能入栈），栈内优先级最低（保证不会被普通运算符弹出）。只有 ) 才能弹出它。理解这一点是正确模拟中缀转后缀的关键。

⚠️ 易错：步骤 4 中的 ≥ 不能改成 >。如果改成严格大于，相同优先级的运算符不会被弹出，会破坏左结合性。例如 a - b + c 应该先算 a-b，如果 + 不弹出 -，就变成先算 b+c 了。

手算示例：a + b * c - (d / e) → a b c * + d e / -

后缀表达式求值#

使用操作数栈：

1. 操作数 → 入栈
2. 运算符 → 弹出两个操作数，先弹出的是右操作数，后弹出的是左操作数，计算结果压回栈
3. 结束 → 栈顶为最终结果

⚠️ 易错：弹出顺序是先右后左。对于减法和除法（不满足交换律），弄反顺序会得到完全不同的结果。例如后缀 5 3 - 应计算 5 - 3 = 2，弄反就变成 3 - 5 = -2。

复杂度#

递归的两个要素#

1. 递归表达式（递归体）：问题可分解为规模更小的同类子问题
2. 边界条件（递归出口）：存在不需要递归就能直接求解的最小规模

1
int Factorial(int n) {
2
    if (n == 0 || n == 1)   // 边界条件
3
        return 1;
4
    return n * Factorial(n - 1);  // 递归表达式
5
}

递归工作原理：系统栈#

每次函数调用时，系统在栈中分配一个栈帧（活动记录），保存：

• 返回地址：调用结束后回到哪里
• 局部变量：本次调用的局部数据
• 参数值：本次调用传入的实参

1
调用过程（入栈）：              返回过程（出栈）：
2
┌─────────────┐              ┌─────────────┐
3
│ Factorial(1) │ → 栈顶      │ return 1    │ → 弹出
4
├─────────────┤              ├─────────────┤
5
│ Factorial(2) │              │ return 2*1  │ → 弹出
6
├─────────────┤              ├─────────────┤
7
│ Factorial(3) │              │ return 3*2  │ → 弹出
8
├─────────────┤              ├─────────────┤
9
│ Factorial(4) │ → 栈底      │ return 4*6  │ → 弹出
10
└─────────────┘              └─────────────┘
11
                             最终结果：24

递归的效率问题#

⚠️ 易错：递归算法的空间复杂度不是调用总次数，而是递归深度（同时存在的最大栈帧数）。Fibonacci(n) 的调用总次数是指数级，但递归深度只有 O(n)，所以空间复杂度是 O(n)。

递归转非递归#

⚠️ 易错：不是所有递归都能简单地用循环替代。树的遍历、图的 DFS 等递归，转非递归时必须用显式栈模拟调用过程。