用于即时评估的调车场算法

Question

通常，计算中缀数学表达式的程序使用调车场算法的一些变体首先将表达式转换为逆波兰表示法，然后计算逆波兰表示法以获得单个最终值。

我的问题是，是否有一些众所周知的算法绕过 INFIX -> RPN 步骤，并使用某种递归下降解析来评估初始中缀表达式？

据推测，在编写编译器或解析器来翻译 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

希望这可以帮助！