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

Question

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

我的问题是，有没有什么著名的算法可以绕过INFIX-

据推测，在编写编译器或解析器来翻译INFIX-

那么，有没有什么众所周知的算法可以在不首先转换为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

希望这能有所帮助！