如何用栈实现逆波兰表达式（RPN）求值

花韻仙語 2026-01-11 00:00:00 次阅读

本文详解如何通过栈结构解析并计算逆波兰表达式（如 "3 23 24 / 34 * 24 / +"），涵盖核心算法逻辑、完整代码实现及关键注意事项。

逆波兰表示法（Reverse Polish Notation, RPN）是一种无需括号、依赖操作数顺序和栈结构进行计算的表达式形式。其求值本质是：遍历每个 token，遇到数字则压栈，遇到运算符则弹出栈顶两个操作数（注意顺序：先弹的是右操作数 b，后弹的是左操作数 a），执行运算后将结果重新压栈；最终栈中唯一剩余元素即为表达式结果。

以示例表达式 "3 23 24 / 34 * 24 / +" 为例，计算流程如下（栈底在左，栈顶在右）：

读到 3 → 栈：[3]
读到 23 → 栈：[3, 23]
读到 24 → 栈：[3, 23, 24]
读到 / → 弹出 b = 24, a = 23 → 计算 a / b = 23 / 24 ≈ 0.9583 → 栈：[3, 0.9583]
读到 34 → 栈：[3, 0.9583, 34]
读到 * → 弹出 b = 34, a = 0.9583 → a * b ≈ 32.5833 → 栈：[3, 32.5833]
读到 24 → 栈：[3, 32.5833, 24]
读到 / → 32.5833 / 24 ≈ 1.3576 → 栈：[3, 1.3576]
读到 + → 3 + 1.3576 = 4.3576 → 栈：[4.3576]

最终结果为 4.3576（保留浮点精度）。

以下是 Python 实现参考（健壮、可扩展）：

def evaluate_rpn(tokens: list[str]) -> float:
    stack = []
    operators = {'+', '-', '*', '/'}

    for token in tokens:
        if token in operators:
            if len(stack) < 2:
                raise ValueError(f"Insufficient operands for '{token}'")
            b = stack.pop()  # 注意：后入先出，b 是右操作数
            a = stack.pop()
            if token == '+':
                result = a + b
            elif token == '-':
                result = a - b
            elif token == '*':
                result = a * b
            elif token == '/':
                if b == 0:
                    raise ZeroDivisionError("Division by zero")
                result = a / b  # 使用真除法（Python 默认）
            stack.append(result)
        else:
            try:
                # 支持整数和浮点数字符串（如 "3", "23", "0.9583"）
                num = float(token) if '.' in token else int(token)
                stack.append(num)
            except ValueError:
                raise ValueError(f"Invalid token: '{token}'")

    if len(stack) != 1:
        raise ValueError("Invalid RPN expression: too many operands or missing operators")

    return stack[0]

# 示例使用
rpn_expr = "3 23 24 / 34 * 24 / +".split()
result = evaluate_rpn(rpn_expr)
print(f"Result: {result:.4f}")  # 输出：Result: 4.3576