表达式求值（栈与数学归纳法）

2026/6/28 · 算法与数据结构

问题简述

在计算机科学中，如何让机器像人一样理解并计算带有括号及不同优先级的算术表达式？例如计算 10 + 5 * 2 / (8 - 3)。

1 问题抽象

主要问题：处理运算优先级（先括号，后乘除，最后加减）。
解决方案：利用栈这一后进先出的数据结构来调整运算顺序。

解决思路

解决表达式求值主要有两种范式：直接计算（双栈法）和形式转换（后缀表达式法）。

1 双栈法 (Double-stack Method)

直接处理中缀表达式（即我们平常用的运算式）。

数据结构设定：
- 数字栈 (num_s)：用于存储操作数。
- 运算符栈 (op_s)：用于存储运算符（+, -, *, /, (）。
核心动作流程：
- 数字处理：读取完整数字并压入数字栈。
- 括号处理：遇到 ( 直接入栈；遇到 ) 则持续弹出运算符并计算，直到遇到 (。
- 优先级比较：遇到运算符 c 时，若其优先级 $\le$ 栈顶运算符优先级，则先弹出栈顶运算符进行计算，再将 c 入栈。
- 优先级定义：+, - 为 1；*, / 为 2。

1.1 例子

输入表达式：10 + 5 * 2 / (8 - 3) 具体过程：

入栈阶段：数字 10 进入数字栈，+ 进入运算符栈；随后 5 进入数字栈。
优先级等待：遇到 *，由于其优先级比栈顶的 + 高，不触发计算，直接入栈
处理括号：遇到 (，开启一个独立的计算子环境
- 计算括号内：读取 8 - 3，遇到 ) 时触发计算，8 - 3 = 5。此时数字栈顶变为 5
依次回溯计算：
- 执行乘法：5 * 2 = 10。
- 执行除法：10 / 5 = 2（此处 5 是括号算出的结果）。
- 执行加法：10 + 2 = 12

最终结果：12

1.2 代码实现

def calculate_two_s(s: str) -> float:
    def compute(op, b, a):
        if op == '+': return a + b
        if op == '-': return a - b
        if op == '*': return a * b
        if op == '/': return a / b
        return 0

    pri = {'+': 1, '-': 1, '*': 2, '/': 2}
    num_s, op_s = [], []
    i, n = 0, len(s)

    while i < n:
        c = s[i]
        if c.isdigit():  # 读取完整多位数字
            j = i
            while j < n and s[j].isdigit():
                j += 1
            num_s.append(float(s[i:j]))
            i = j
        elif c == '(':
            op_s.append(c) # 隔离重新开启一个计算子式
            i += 1
        elif c == ')':  # 计算括号内的所有运算
            while op_s and op_s[-1] != '(':
                op = op_s.pop()
                b = num_s.pop()
                a = num_s.pop()
                num_s.append(compute(op, b, a))
            op_s.pop()  # 弹出 '('
            i += 1
        elif c in '+-*/':
            # 当前运算符c优先级 <= 栈顶优先级时，先算栈顶
            while (op_s and op_s[-1] != '(' and 
                   pri[c] <= pri.get(op_s[-1], 0)):
                op = op_s.pop()
                b = num_s.pop()
                a = num_s.pop()
                num_s.append(compute(op, b, a))
            op_s.append(c)
            i += 1
        else:
            i += 1  # 跳过空格等

    # 处理剩余的运算符
    while op_s:
        op = op_s.pop()
        b = num_s.pop()
        a = num_s.pop()
        num_s.append(compute(op, b, a))

    return num_s if num_s else 0

2 中缀转后缀 (Infix to Postfix/RPN)

将中缀表达式转换为逆波兰表达式（RPN），其优点是无需括号即可表达运算优先级。

转换逻辑：
- 数字直接输出到结果列表。
- 利用栈暂存运算符，并根据优先级决定输出顺序。
- 转换后的序列可直接顺序读取并利用单栈轻松计算结果。

2.1 例子

步骤一：转换序列

按照算法逻辑，将 10 + 5 * 2 / (8 - 3) 转换为后缀序列：10 5 2 * 8 3 - / +

步骤二：计算结果

从左向右扫描转换后的序列：
- 遇到 10, 5, 2：全部入栈。
- 遇到 *：弹出 5 和 2，算得 10 入栈。
- 遇到 8, 3：入栈。
- 遇到 -：弹出 8 和 3，算得 5 入栈。
- 遇到 /：弹出 10 和 5，算得 2 入栈。
- 遇到 +：弹出 10 和 2，算得 12。

2.2 代码实现

def infix2rpn(s: str) -> list:
    pri = {'+': 1, '-': 1, '*': 2, '/': 2}
    output = []
    stack = []
    i, n = 0, len(s)

    while i < n:
        c = s[i]
        if c.isdigit(): # 读取完整数字
            j = i
            while j < n and s[j].isdigit():
                j += 1
            output.append(float(s[i:j]))
            i = j
            continue # 数字处理完直接进入下一轮循环
        elif c == '(':
            stack.append(c)
        elif c == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop() # 弹出 '('
        elif c in '+-*/':
            while stack and stack[-1] != '(' and pri.get(stack[-1], 0) >= pri[c]:
                output.append(stack.pop())
            stack.append(c)
        i += 1

    while stack:
        output.append(stack.pop())
    
    return output

理论证明工具：数学归纳法

为了分析算法的可解性与泛化能力，需要严谨的证明手段。

1 普通归纳法 (Ordinary Induction)

基础步骤：验证 $n = n_0$ （通常为0或1）时命题成立。
归纳步骤：假设 $n = k$ 时成立，证明 $n = k+1$ 时也成立。

1.1 例子：前n个自然数之和

命题：证明前 n 个自然数之和公式，即对于所有正整数 n，都有 1 + 2 + 3 + ... + n = n(n+1)/2

基础步骤：验证 n = 1 时等式成立。左边：1 右边：1 × (1+1) / 2 = 2/2 = 1 左边等于右边，所以命题 P(1) 成立。
归纳步骤：假设当 n = k（k ≥ 1）时命题成立，即假设 1 + 2 + ... + k = k(k+1)/2 成立我们需要证明当 n = k+1 时命题也成立，即证明 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2 根据归纳假设，我们可以将前 k 项替换： 1 + 2 + … + k + (k+1) = k(k+1)/2 + (k+1) = [k(k+1) + 2(k+1)] / 2 = (k+1)(k+2) / 2 得到的右边恰好是 P(k+1) 的形式。

由基础和归纳步骤，根据普通数学归纳法原理，命题对所有正整数 n 成立。最终结果：1 + 2 + ... + n = n(n+1)/2

2 强数学归纳法 (Strong Induction)

原理：假设对于所有 $n_0 \le m \le k$ 的情况都成立，以此证明 $k+1$ 成立。
意义：在分析复杂算法（如卡特兰数相关的树结构或递归问题）时，强归纳法提供了更强大的推理能力。

2.1 例子：卡特兰数

卡特兰数 $C_n$ 的递推定义（括号匹配、二叉树计数等）： $C_0 = 1$ ，且对于 $n \ge 0$ ，有 $C_{n+1} = \sum_{i=0}^{n} C_i \cdot C_{n-i}$ 。

由此可算出： $C_0=1,\ C_1=1,\ C_2=2,\ C_3=5,\ C_4=14,\ \cdots$

命题：使用强数学归纳法证明，对于所有正整数 $n \ge 1$ ，卡特兰数满足下界不等式： $C_n \ge 2^{n-1}$

基础步骤：验证 $n = 1$ 时不等式成立。 $C_1 = C_0 \cdot C_0 = 1 \times 1 = 1$ 右边： $2^{1-1} = 2^0 = 1$ 所以 $C_1 \ge 1$ 成立，命题 $P(1)$ 为真。
归纳步骤：假设命题对所有小于等于 $n$ 的正整数都成立，即对于所有 $1 \le k \le n$ ，都有 $C_k \ge 2^{k-1}$ 我们需要证明 $P(n+1)$ 成立，即证明： $C_{n+1} \ge 2^{n}$ 根据卡特兰数的递推定义： $C_{n+1} = \sum_{i=0}^{n} C_i \cdot C_{n-i}$ 展开这个和式（重点关注两头，即 $i=0$ 和 $i=n$ 的项）： $C_{n+1} = C_0 C_n + C_1 C_{n-1} + \cdots + C_{n-1} C_1 + C_n C_0$ 由于式中所有项都是正数（卡特兰数均为正整数），因此和式必然大于等于它的前两项之和（即 $i=0$ 与 $i=n$ ）： $C_{n+1} \ge C_0 C_n + C_n C_0$ 已知 $C_0 = 1$ ，所以： $C_{n+1} \ge 1 \cdot C_n + C_n \cdot 1 = 2 C_n$ 现在利用强归纳假设中的 $k = n$ 这一条（因为 $n \le n$ 显然成立），我们有： $C_n \ge 2^{n-1}$ 将其代入上式： $C_{n+1} \ge 2 \cdot C_n \ge 2 \cdot 2^{n-1} = 2^{n}$ 最终得到： $C_{n+1} \ge 2^{n}$ ，这正是 $P(n+1)$ 需要证明的结论。

分析与总结

栈的价值：它是处理“嵌套”逻辑（如括号、函数嵌套）的天然工具。
理论与实践结合：算法的正确性由数学归纳法保证，而效率则通过选择合适的数据结构（如栈）来提升。