逆波兰表示法：求值数学表达式的优雅替代方案

什么是逆波兰表示法？

RPN 是一种数学表示法，其中运算符位于其运算数之后。在 RPN 中，我们不写 A + B，而是将其表示为 A B +。乍一看可能有些不寻常，但它的优点很快就会显现出来。

RPN 的概念起源于波兰数学家扬·武卡谢维奇，他在 20 世纪 20 年代开发了前缀表示法（波兰表示法），其中运算符位于其运算数之前。后缀表示法是前缀表示法的一种变体，由澳大利亚计算机科学家查尔斯·汉布林在 20 世纪 50 年代进一步发展，以简化计算机处理。

为什么 RPN 有用？

RPN 的主要优点是消除歧义和计算效率。中缀表示法需要括号来明确运算顺序，而计算机需要复杂的解析算法才能正确处理运算符优先级。然而，在 RPN 中，括号是不必要的，运算顺序由表达式的结构自动确定。

这对于早期硬件资源有限的计算机和袖珍计算器尤为重要。使用 RPN 的计算器可以更简单、更快速地执行计算。

历史花絮： RPN 表示法最初由惠普 (HP) 公司在 20 世纪 60 年代和 70 年代推广开来。HP-9100A 台式计算器 (1968) 是首批使用 RPN 的商用计算器之一。后来，传奇的 HP-35 (1972)——第一款科学袖珍计算器，也采用了 RPN，这种方法长期以来一直是惠普专业计算器的标志。RPN 计算器以其快速准确的计算而闻名，并在工程师、科学家和金融专业人士中广受欢迎。

RPN 的工作原理

现在，让我们看看如何使用堆栈来求值这个 RPN 表达式。堆栈是一种数据结构，可以将元素放入（入栈）和移除（出栈），始终先取出最后插入的元素（LIFO - 后进先出）。

RPN 表达式的逐步求值：

如何将中缀表达式转换为 RPN？

将中缀表达式转换为 RPN 最常见的算法是调度场算法，由埃德斯加·戴克斯特拉开发。该算法使用堆栈（用于运算符和括号）和输出队列（在实践中可以只是一个列表）进行转换。

调度场算法的步骤：

1. 词法分析： 将中缀表达式分解为词法单元（数字、运算符、括号）。
2. 初始化： 创建一个空堆栈用于存储运算符，并创建一个空输出队列用于构建 RPN 表达式。
3. 处理词法单元： 遍历词法单元：
   • 数字： 如果词法单元是数字，则将其添加到输出队列。
   • 运算符 (op1)： 如果词法单元是运算符：
     • 当堆栈顶部存在运算符 (op2)，并且满足以下任一条件时：
       • op2 的优先级高于 op1，或者
       • op2 的优先级等于 op1 且 op1 是左结合的（在我们的示例中，所有运算符都是左结合的），
     • 从堆栈中弹出 op2 并将其添加到输出队列。
     • 将 op1 压入堆栈。
   • 左括号 (： 将其压入堆栈。
   • 右括号 )：
     • 当堆栈顶部的运算符不是左括号时：
       • 从堆栈中弹出运算符并将其添加到输出队列。（如果在找到左括号之前堆栈变为空，则存在不匹配。）
     • 如果堆栈顶部存在左括号，则从堆栈中弹出它（但不要将其添加到输出队列——括号不包含在 RPN 表达式中）。
     • 如果在处理右括号后，堆栈顶部不是左括号，则括号不匹配。
4. 清空堆栈： 当没有更多词法单元要读取时，从堆栈中弹出任何剩余的运算符并将其添加到输出队列。
5. 结果： 输出队列现在包含 RPN 表达式。

优先级和结合性：

理解运算符优先级和结合性非常重要。通常的优先级顺序（从高到低）：