调车场算法的即时评估

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

希望这对你有帮助!