Expression evaluation

Question

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?

Answer 1

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.