3

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

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

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

那么，是否有任何众所周知的算法来解析中缀表达式而不首先转换为 RPN？还是转换为 RPN 通常比任何其他方法更有效？

4

1 回答 1

5

您可以轻松地修改 shutting-yard 算法，以便在进行时立即评估表达式，而不是构建 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

希望这可以帮助！

于 2014-05-25T17:41:16.477 回答