algorithm - 用于立即评估的调车场算法

Question

通常，评估中缀数学表达式的程序使用 Shunting Yard Algorithm 的一些变体 首先将表达式翻译成 Reverse Polish Notation ，然后计算反向波兰表示法以获得单个最终值。

我的问题是，是否有一些著名的算法可以绕过 INFIX -> RPN 步骤，并使用某种递归下降解析来评估初始的 infix 表达式？

据推测，它可能在编写编译器或解析器以翻译 INFIX -> RPN 时有用。 RPN 是一种表达式的“编译形式”(AST)，计算机可以使用简单的输出堆栈更轻松地对其进行评估。但是，如果您只是简单地编写立即将中缀表达式转换为数字输出值的代码，那么缓存中间 RPN 形式可能没有任何用处。

那么，有没有什么著名的算法可以在不首先转换为 RPN 的情况下解析中缀表达式？或者转换为 RPN 通常比任何其他方法更有效？

Answer 1

您可以轻松修改调车场算法，以便在您进行时立即评估表达式，而不是构建 RPN 表示。具体来说，只要您通常从堆栈中弹出一个运算符和两个操作数，而不是将这些标记附加到输出，而是只计算表达式并将结果推回操作数堆栈。最后，在最后，通过弹出两个操作数、弹出一个运算符、计算结果并将其推回堆栈来评估运算符和操作数堆栈隐含的表达式。

例如，要计算 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

希望这对您有所帮助!