views:

52

answers:

2

I am trying to evaluate a list that represents an expression in prefix notation. Here is an example of such a list:

[+, [sin, 3], [- 10 5]]

What is the best way to evaluate the value of the list

+2  A: 

KISS, evaluate in reverse as a postfix expression.

paul
A: 

It will be simpler if you used postfix instead of prefix. See Reverse Polish Notation (RPN). Given an expression in RPN, it is easy to evaluate that using just one stack.

But since you asked for a way to evaluate prefix expressions without recursion and using stacks (for a possibly simpler way, see EDIT: below), here is one way:

We can do this using two stacks.

One stack (call it Evaluation) holds the operators (like +, sin etc) and operands (like 3,4 etc) and the other stack (call it Count) holds a tuple of the number of operands left to be seen + the number of operands an operator expects.

Anytime you see an operator, you push the operator onto the Evaluation stack and push the corresponding tuple onto the Count stack.

Anytime you see an operand (like 3,5 etc), you check the top tuple of the Count stack and decrement the number of operands left to be seen in that tuple.

If the number of operands left to be seen becomes zero, you pop the tuple from the Count stack. Then from the Evaluation stack you pop off the number of operands required (you know this because of the other value of the tuple), pop off the operator and do the operation to get a new value, (or operand).

Now push the new operand back on the Evaluation stack. This new operand push causes you to take another look at the top of the Count stack and you do the same thing we just did (decrement the operands seen, compare with zero etc).

If the operand count does not become zero, you continue with the next token in the input.

For example say you had to evaluate + 3 + 4 / 20 4

The stacks will look like (left is the top of the stack)

Count                  Evaluation                   Input
                                                   + 3 + 4 / 20 4

(2,2)                   +                            3 + 4 / 20 4

(2,1)                   3 +                            + 4 / 20 4

(2,2) (2,1)             + 3 +                            4 / 20 4

(2,1) (2,1)             4 + 3 +                            / 20 4

(2,2) (2,1) (2,1)       / 4 + 3 +                            20 4

(2,1) (2,1) (2,1)       20 / 4 + 3 +                            4

(2,0) (2,1) (2,1)       4 8 / 4 + 3 +                   

Since it has become zero, you pop off two operands, the operator / 
and evaluate and push back 5. You pop off (2,0) from the Count stack.

(2,1) (2,1)                5 4 + 3 +

Pushing back you decrement the current Count stack top.

(2,0) (2,1)               5 4 + 3 + 

Since it has become zero, you pop off 5,4 and + and evaluate and push back 9. 
Also pop off (2,0) from the count stack.

(2,0)                          9 3 + 

                               12

EDIT:

A friend suggested a way to do this without multiple stacks:

Start from the end, go to the first operator. The tokens to the right of that will be operands. Evaluate and redo. Seems much simpler than doing it with two stacks. We can use a doubly linked list to represent the input which we change during processing. When you evaluate, you delete nodes, and then insert the result. Or you could perhaps just use one stack.

Moron
Thanks so much- this is exactly what is was looking for. Out of curiosity, would it be difficult to convert from prefix to postfix notation?
ad126
@ad126: It might get tricky as just reversing once won't do. You have to convert each sublist too. If you have to do that (i.e. you cannot avoid prefix), you might as well just use the above one pass algorithm instead of trying to convert to postfix and then use the RPN evaluator.
Moron
Word, Moron. Thanks for your help.
ad126
@ad126: A friend suggested a simpler way which you might find easier to implement (though I haven't tried to verify correctness). I have edited the answer to include that (and might actually even be what Paul intended to say).
Moron