How to evaluate an expression in prefix notation

Question

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

Answer 1

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.