3

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

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

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

Evaluate("3 * 5")

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

Evaluate("2 + 15")

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

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

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

4

4 回答 4

2

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

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

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

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

例如一个非常简单的例子，带有 '+' 和 '*'

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

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

你可以使用 Antlr 来做一个像这样的非常简单的语法，然后看看它生成了什么代码——在这种情况下它会是非常短的代码，所以很容易理解。

如果你的语法会变得复杂，我会鼓励你使用像 Antlr 这样的工具，因为它消除了解析代码中的大量繁重工作——这种东西已经完成了数百次之前而且很机械。它使您可以专注于您想要对表达式执行的有趣的事情。

于 2011-01-16T19:35:42.300 回答
2

使用波兰表示法可能会有所帮助：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 步的结果压入操作数堆栈。

我过度简化了一些事情，可能遗漏了一些步骤，因此仅以此作为起点。有些细节我已经跳过/不记得很多了。其中一些内容包括二元或一元运算符、如何处理括号、如何处理幂计算等等。

希望这会有所帮助，祝你好运:)

于 2011-01-16T20:20:26.920 回答
1

无论如何，您必须递归。所以即使你看到一个 + 你也必须递归。本质上，您必须将所有没有括号的二元运算符视为有括号。

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

于 2011-01-16T19:35:45.410 回答
0

搜索您的最高优先级运算符并首先执行此操作，然后继续。因此，如果您只有 + 和 *，则搜索 * 的实例并将子字符串 aaaa * bbbb 替换为 aaaa * bbbb 的值。一旦没有此类实例，请继续使用 +。

如果给定运算符中的顺序很重要（例如，如果包含 ^），则您必须决定从这些运算符开始的位置。

于 2011-01-16T19:36:04.350 回答