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

Was it helpful?

Solution

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.

OTHER TIPS

KISS, evaluate in reverse as a postfix expression.

The way I see it you have two options. Either go left to right or right to left (as paul suggested above). Both methods are demonstrated in the code below.

public static class Evaluator
{
   public static double EvaluatePrefix(string expr)
   {
       if (expr == null) throw new ArgumentNullException("expr");

       var symbols = expr.Split(',');
       var stack = new Stack<Symbol>();

       foreach (var symbol in symbols)
       {
           double operand;
           if (!double.TryParse(symbol, out operand)) //encountered an operator
           {
               stack.Push(new Operator(symbol));
               continue;
           }

           //encountered an operand
           if (stack.Count == 0) throw new ArgumentException("Invalid expression");

           double right = operand;
           var leftOperand = stack.Peek() as Operand;
           while (leftOperand != null)
           {
               stack.Pop(); //pop left operand that we just peeked
               if (stack.Count == 0) throw new ArgumentException("Invalid expression");
               double result = Calculate(leftOperand.Value, right, ((Operator)stack.Pop()).OperatorChar);

               right = result;
               leftOperand = (stack.Count == 0) ? null : stack.Peek() as Operand;
           }
           stack.Push(new Operand(right));
       }

       if (stack.Count != 1) throw new ArgumentException("Invalid expression");
       var operandSymbol = stack.Pop() as Operand;
       if (operandSymbol == null) throw new ArgumentException("Invalid expression");
       return operandSymbol.Value;
   }

   public static double EvaluatePrefixAlternative(string expr)
   {
       if (expr == null) throw new ArgumentNullException("expr");

       double d;
       var stack = new Stack<Symbol>(
           expr.Split(',').Select(s => double.TryParse(s, out d) ? (Symbol) new Operand(d) : new Operator(s)));

       var operands = new Stack<double>();
       while (stack.Count > 0)
       {
           var symbol = stack.Pop();
           var operand = symbol as Operand;
           if (operand != null)
           {
               operands.Push(operand.Value);
           }
           else
           {
               if (operands.Count < 2) throw new ArgumentNullException("expr");
               operands.Push(Calculate(operands.Pop(), operands.Pop(), ((Operator) symbol).OperatorChar));
           } 
       }

       if (operands.Count != 1) throw new ArgumentNullException("expr");
       return operands.Pop();
   }

   private static double Calculate(double left, double right, char op)
   {
       switch (op)
       {
           case '*':
               return (left * right);
           case '+':
               return (left + right);
           case '-':
               return (left - right);
           case '/':
               return (left / right); //May divide by zero !
           default:
               throw new ArgumentException(string.Format("Unrecognized operand {0}", op), "op");
       }
   }

   abstract class Symbol
   {
   }

   private class Operand : Symbol
   {
       public double Value { get; private set; }

       public Operand(double value)
       {
           Value = value;
       }
   }

   private class Operator : Symbol
   {
       public char OperatorChar { get; private set; }

       public Operator(string symbol)
       {
           if (symbol.Trim().Length != 1) throw new ArgumentException("Invalid expression");
           OperatorChar = symbol[0];
       }
   }
}

Some tests:

[TestMethod]
public void TestPrefixEvaluation()
{
  Assert.AreEqual(5, Evaluator.EvaluatePrefix("-,*,/,15,-,7,+,1,1,3,+,2,+,1,1"));
  Assert.AreEqual(4, Evaluator.EvaluatePrefix("/,-,*,2,5,*,1,2,-,11,9"));
  Assert.AreEqual(5, Evaluator.EvaluatePrefixAlternative("-,*,/,15,-,7,+,1,1,3,+,2,+,1,1"));
  Assert.AreEqual(4, Evaluator.EvaluatePrefixAlternative("/,-,*,2,5,*,1,2,-,11,9"));
}
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top