Shunting Yard算法用于立即求值

Question

通常，计算中缀数学表达式的程序使用 Shunting Yard Algorithm 的某种变形来先将表达式转换为 Reverse Polish Notation，然后再计算 Reverse Polish Notation 得出单个最终值。

我的问题是，是否有一些著名算法可以跳过 INFIX -> RPN 步骤，直接使用某种递归下降解析方法在原地计算初始的中缀表达式？

想必，在编写编译器或解析器以将 INFIX 转换为 RPN 时，这可能非常有用。RPN 是表达式（AST）的"编译形式"，可以通过简单的输出堆栈更轻松地由计算机进行评估。但如果您只是编写立即将中缀表达式转换为数字输出值的代码，则可能没有任何用处缓存中间RPN格式。

因此，是否有任何著名的算法用于分析中缀表达式，而不是首先转换为 RPN？还是将其转换为 RPN 通常比其他方法更有效？

- Siler

---

如果你需要多次评估一个方程，逆波兰表示法（RPN）将是一个更快的解决方案，因为你不需要进行太多的处理。你还可以修改Shunting Yard算法，直接生成一个抽象语法树（AST），这对于除了评估之外的任何其他操作都非常方便。 - Salix alba

Answer 1

你可以很容易地修改Shunting-yard算法，以便在构建逆波兰表示式的同时立即评估表达式。具体来说，每当你通常从栈中弹出一个运算符和两个操作数时，不要将这些令牌附加到输出中，而是直接评估表达式并将结果推回到操作数栈。最后，在最后一步，通过弹出两个操作数、弹出一个运算符、计算结果并将其推回到栈中，评估由运算符和操作数堆栈隐含的表达式。

例如，要计算3 * 4 + 2，你需要执行以下步骤：

Process 3:
  Operators  
  Operands    3

Process *:
  Operators   *
  Operands    3

Process 4:
  Operators   *
  Operands    3 4

Process +:
  Operators   +
  Operands    12

Process 2:
  Operators   +
  Operands    12 2

End of input:
  Operators   
  Operands    14

希望这能帮到您！

- templatetypedef