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

Search for your highest-precedence operator and do that first, then move on. So if you have only + and *, search for instances of * and replace the substring aaaa * bbbb with the value of aaaa * bbbb. Once no such instances remain, work on +.

If order within a given operator matters (for example, if you include ^) you'll have to decide where to start with those operators.

Answer 2

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.

Answer 3

You must recurse anyways. So even when you see a + you must recurse. In essence you must treat all binary operators that do no have parenthesis as having them.

2 + 3 * 5 really is 2 + (3 * 5).

Answer 4

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:

1. If you run into an operator, push it onto the operator stack
2. If you run into and operand (number) push it onto the operand stack
3. 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.
4. 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 :)