5

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

4
  • why do you need brackets then?
    – Andrey
    Jul 8, 2010 at 16:17
  • 2
    If it can be expressed with recursion it can be expressed with a stack.
    – KLee1
    Jul 8, 2010 at 16:20
  • 2
    No it's not homework- I'm trying to implement Karl Sim's genetic programming technique (karlsims.com/papers/siggraph91.html), which uses Lisp s-expressions, in python.
    – ad126
    Jul 8, 2010 at 17:09
  • Just curious @ad126 -- have you done this in python ? Can you share or point me to any source code for this genetic programming technique ? thanks
    – zubinmehta
    Sep 20, 2015 at 7:15

3 Answers 3

10

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.

4
  • 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
    Jul 8, 2010 at 19:18
  • @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.
    – Aryabhatta
    Jul 8, 2010 at 19:28
  • Word, Moron. Thanks for your help.
    – ad126
    Jul 8, 2010 at 19:31
  • @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).
    – Aryabhatta
    Jul 8, 2010 at 20:35
6

KISS, evaluate in reverse as a postfix expression.

1
  • 5
    Yes, but you'd have to reverse the operands' order. Otherwise [/, 1, 2] will be evaluated as 2 instead of 1/2. Dec 8, 2012 at 20:02
1

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"));
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.