algorithm - 表达式评估

Question

我正在做一个表达式估值程序，就像this .我的问题是我不知道如何处理操作优先级。我使用递归找到最里面的一对括号，找到后解决其中的表达式，如下所示:

Evaluate("2 + (3 * 5)")

会这样重新调用自己:

Evaluate("3 * 5")

现在，由于没有括号，它会计算结果并再次调用自己:

Evaluate("2 + 15")

OK，返回值为17，符合预期。但是如果我调用 Evaluate("2 + 3 * 5")，结果是:

Evaluate("2 + 3 * 5")
Evaluate("5 * 5")

这显然是错误的。
基本上我是从左到右解决操作。如何选择必须首先执行的操作？我想在每个操作周围添加几个括号，但它看起来不太好。
那么，我需要先解析整个表达式吗？还有另一种方法吗？

Answer 1

这是一篇很好的文章，展示了如何使用 Antlr 和 .net 来完成这种事情。

http://www.codeproject.com/KB/recipes/sota_expression_evaluator.aspx

听起来您想手写解析器，但这将为您提供了解如何正确执行此操作所需的一切。

基本上，您可以通过将表达式定义为一系列可能的操作来实现优先级，其中每个操作都在下一级进行操作。然后按此序列的顺序对操作的优先级进行编码。

例如使用“+”和“*”的非常简单的示例

additiveExpression: multiplicativeExpression '+' multiplicativeExpression
multiplicativeExpression: number '*' number

您手写的递归下降解析器从最上面的规则开始并向下工作。

您可以使用 Antlr 来执行这样一个非常简单的语法，然后查看它生成的代码 - 在这种情况下它会是非常短的代码，因此非常容易理解。

如果您的语法会以任何方式变得复杂，我会鼓励您无论如何使用像 Antlr 这样的工具，因为它消除了解析代码中的许多繁重工作 - 这是已经完成的事情数百次之前，非常机械。它让您专注于您想用表达式做的有趣事情。