表达评估

发布于 2024-10-12 17:22:25 字数 601 浏览 3 评论 0原文

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

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

将这样重新调用自身：

Evaluate("3 * 5")

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

Evaluate("2 + 15")

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

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

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

原文

I'm doing an expression valuation program, just like this. My problem is that I can't figure out how to handle operation precedences. I used recursion to find the innermost couple of parenthesis and, when found, solve the expression inside them, like this:

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

will re-call itself this way:

Evaluate("3 * 5")

now, since there aren't parenthesis, it calculates the result and calls itself another time:

Evaluate("2 + 15")

Ok, the return value is 17, as expected. But if I call Evaluate("2 + 3 * 5") the result is:

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

Which is clearly wrong.
Basically I'm solving operations from left to right. How can I chose the operations that must be performed first? I was thinking to add a couple of parenthesis surrounding every operation, but it doesn't look so good.
So, do I need to parse the whole expression first o there's another way?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

平定天下 2024-10-19 17:22:25

这是一篇很好的文章，展示了如何使用 Antlr 和 .net 来完成此类操作。

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

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

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

例如，一个带有“+”和“*”的非常简单的示例

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

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

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

如果你的语法会变得复杂，我会鼓励你使用像 Antlr 这样的工具，因为它消除了解析代码中的大量繁重工作 - 这种事情已经完成了数百次之前并且非常机械。它让您能够专注于您想要用表达式做的有趣的事情。

Here is a nice article showing how to do this kind of thing using Antlr with .net.

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

It sounds like you want to hand write your parser, but this will give you all you need to see how to do this correctly.

Basically you implement precedence by defining the expression as a sequence of possible operations where each operation operates on the next level down. The precedence of the operations is then encoded in the order of this sequence.

E.g. a very simple example with '+' and '*'

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

Your hand written recursive descent parser starts at the top rule and works down.

You could use Antlr to do a very simple grammer like this and then see what code it generates - it would be very short code in this case and so be very easy to follow.

If your grammer is going to get in any way complicated I would encourage you to use a tool like Antlr anyway, as it takes away a lot of the heavy lifting in the parsing code - it's the kind of stuff that has been done hundreds of times before and is very mechanical. It leaves you to focus on the interesting stuff that you want to do with the expressions.

回复收藏 0 原文

逐鹿 2024-10-19 17:22:25

可以帮助的是使用波兰表示法： 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

我最初几次进行这些转换时，我对它们感到非常困惑。如果它也适合您，请不要被吓倒，继续练习即可。好处是您可以找到算法来帮助您完成此转换，因此这应该会有所帮助。

进行这种转换的一大优点是可以从左到右计算修改后的表达式。该算法的运行方式如下：

维护两个堆栈 - 一个用于运算符，一个用于操作数。
从左到右求值：

如果遇到操作符，则将其压入操作数堆栈
如果遇到操作数（数字），则将其压入操作数堆栈
一旦为最顶层的操作符（两个在大多数情况下），查看运算符并对两个操作数执行该操作。
将步骤 #3 的结果推入操作数堆栈。

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

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

Something that could help is the use of Polish Notation: http://en.wikipedia.org/wiki/Polish_notation#Computer_programming. This notation allows you to not require parentheses and helps you with order of operations.

What's nice about the use of this is that there are algorithms to evaluate these kinds of expressions. It's also possible to convert an infix expression into a prefix or postfix expression.

Here's an example of how it can be done - Lets take your example "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

The first couple of times I did these conversions, I was very confused by them. If it does for you too, don't be intimidated and just keep practicing. What's nice is that you can find algorithms to help you do this conversion, so that should help a bit.

The big advantage to doing this conversion is that one can evaluate the modified expression from left-to-right. The algorithm runs something like this:

Maintain two stacks - one for operators and one for operands.
Evaluation from left-to-right:

If you run into an operator, push it onto the operator stack
If you run into and operand (number) push it onto the operand stack
Once you've found enough operands for the topmost operator (two in most cases), look at the operator and perform that operation on the two operands.
Push the result of step #3 onto the operand stack.

I've oversimplified some things and may have missed some steps, so use this only as a starting point. There are details I've skipped/don't remember a ton about. Some of those things include are the operators binary or unary, how do you handle parentheses, how do you handle evaluation of powers, and more.

Hope this helps and good luck :)

回复收藏 0 原文