表达式求值

Question

我正在编写一个表达式计算程序，就像这个一样。我的问题是我不知道如何处理运算符的优先级。我使用递归来查找最内层的括号，并在找到后解决其中的表达式，就像这样：

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

将以这种方式重新调用自身：

Evaluate("3 * 5")

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

Evaluate("2 + 15")

好的，返回值是17，跟预期一样。但如果我调用Evaluate("2 + 3 * 5")，结果是：

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

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

- BlackBear

---

可能是编写简单的方程解析器的重复问题。 - Saeed Amiri

Answer 1

有一个能够帮助的方法是使用波兰符号表示法：http://en.wikipedia.org/wiki/Polish_notation#Computer_programming。这种表示法允许你不需要括号，并且可以帮助你确定运算顺序。

使用这种表示法的好处是有算法来计算这些表达式。同时，也可以将中缀表达式转换为前缀或后缀表达式。

以下是一个示例，说明如何进行操作——假设我们有一个例子：“2 + 3 * 5”。

2 + 3 * 5
b = 3 * 5
    -convert b-
b = * 3 5
2 + b
    -convert expression-
+ 2 b
    -expand b-
+ 2 * 3 5

我第一次进行这些转换时，非常困惑。如果您也有同样的问题，请不要感到害怕，继续练习即可。好处是，您可以找到算法来帮助您进行此转换，这应该会有所帮助。

进行此转换的重大优势在于，可以从左到右评估修改后的表达式。算法运行如下：

维护两个堆栈——一个用于运算符，一个用于操作数。 从左到右进行评估：

1. 如果遇到运算符，请将其推入运算符堆栈。 2. 如果遇到操作数（数字），请将其推入操作数堆栈。 3. 一旦您找到足够的操作数以供最上面的运算符使用（在大多数情况下为两个），请查看运算符并在两个操作数上执行该操作。 4. 将步骤＃3的结果推送到操作数堆栈上。

我已经简化了一些事情，可能错过了一些步骤，因此仅将其用作起点。我跳过/不记得很多细节。其中一些内容包括运算符是二元还是一元，如何处理括号，如何处理幂的评估等等。

希望这可以帮助您，祝您好运 :)

- pseudoramble

---

没错。我认为这将是第二步，因为我应该完全改变我的例程。谢谢 ;) - BlackBear

Answer 2

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

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

听起来你想要手写解析器，但是这会给你展示正确方法的所有需要。

基本上，你通过定义表达式作为一系列可能的操作来实现优先级，每个操作都在下一层上运行。操作的优先级则编码在这个序列的顺序中。

例如，一个非常简单的例子是'+'和'*'。

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

你手写的递归下降解析器从顶级规则开始向下工作。

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

如果你的语法变得复杂，我仍然建议你使用类似Antlr这样的工具，因为它可以减轻很多解析代码的重负 - 这是已经做过数百次的机械化的工作。这让你专注于想要对表达式执行的有趣的事情。

- James Gaunt

---

我会查看，但是链接丢失了 ;) - BlackBear

Answer 3

无论如何，您都必须进行递归。因此，即使您看到一个 +，您也必须进行递归。实质上，您必须将所有没有括号的二元运算符视为具有括号。

2 + 3 * 5 实际上是 2 + (3 * 5)。

- AbstractDissonance

---

@BlackBear：不行。你必须以优先级（和结合性）为考虑因素进行解析，以产生一个明确的表示形式（中缀带括号到处都是可以满足这一点，但RPN或AST更容易，因为你必须生成某种中间表示形式），然后你可以进行评估。有相应的算法（如果你坚持使用表达式，那么Shunting Yard算法非常简单且强大）。 - user395760

Answer 4

搜索您最高优先级的运算符并首先执行它，然后继续下一个。因此，如果您只有+和*，请搜索*的实例，并用aaaa * bbbb的值替换子字符串aaaa * bbbb。一旦没有这样的实例，就可以处理+。

如果给定运算符内部的顺序很重要（例如，如果包括^），则必须决定从哪些运算符开始。

- Charles

---

谢谢。虽然还有更多技术性的答案，但我觉得你的最简单。 - BlackBear