如何用栈求解逆波兰表达式（RPN）的最终值

心靈之曲 2026-01-11 00:00:00 次阅读

本文详解如何通过栈结构解析并计算逆波兰表达式（如 `"3 23 24 / 34 * 24 / +"`），逐步演示入栈、出栈、运算与结果合并的完整流程，并提供可直接运行的 python 实现。

逆波兰表示法（RPN）的核心思想是操作符后置，所有计算均依赖一个操作数栈：遇到数字则压入栈；遇到运算符（如 +, -, *, /）则从栈中弹出两个操作数（注意顺序：先弹出的是右操作数，后弹出的是左操作数），执行运算后将结果重新压入栈。最终栈中仅剩一个值，即为整个表达式的计算结果。

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

步骤	当前元素	栈状态（由底→顶）	说明
1	3	[3]	数字，入栈
2	23	[3, 23]	入栈
3	24	[3, 23, 24]	入栈
4	/	[3, 0.9583...]	弹出 24（b）、23（a），计算 a / b = 23 / 24 ≈ 0.9583，压入
5	34	[3, 0.9583..., 34]	入栈
6	*	[3, 32.5833...]	弹出 34（b）、0.9583...（a），计算 a * b ≈ 32.5833，压入
7	24	[3, 32.5833..., 24]	入栈
8	/	[3, 1.3576...]	弹出 24（b）、32.5833...（a），计算 a / b ≈ 1.3576，压入
9	+	[4.3576...]	弹出 1.3576...（b）、3（a），计算 a + b ≈ 4.3576，压入

最终栈顶即为结果：≈ 4.3576（与原中缀表达式 3 + (23/24) * 34 / 24 的数学结果一致）。

以下是简洁可靠的 Python 实现（支持 +, -, *, /，自动处理浮点精度）：

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

    for token in tokens.split():
        if token not in operators:
            stack.append(float(token))
        else:
            b = stack.pop()  # 右操作数（先弹出）
            a = stack.pop()  # 左操作数（后弹出）
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a / b)  # 注意：Python 中 / 默认返回 float

    return stack[0]

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