Evaluating postfix expression using stack

We have seen the conversion of infix to postfix expression here. Now lets  see how to evaluate it.

Algorithm

1. Scan input expression from left to right
• If scanned input is an operand, push it into the stack
• If scanned input is an operator, pop out two values from stack. Then, perform operation between popped values and then push back the result into the stack.
2. Repeat above two steps till all the characters are scanned.
3. After all characters are scanned, there will be only one element in the stack, and this is the result of given expression.

Note that here we are having operand stack, but while conversion to postfix from infix, we had operator stack.

Pseudocode
Here is the pseudocode for the same.

evaluatePostfix(postfix) // Evaluates a postfix expression.
valueStack = a new empty stack
while (postfix has characters left to parse)
{ nextCharacter = next nonblank character of postfix
  switch (nextCharacter)
  { 
    case variable:
         valueStack.push(value of the variable nextCharacter)
         break;
  case '+': case '-': case '*': case '/': case '^':
         operandTwo = valueStack.pop()
         operandOne = valueStack.pop()
         result = the result of the operation in nextCharacter and 
                 its operands operandOne and operandTwo
         valueStack.push(result)
         break;
  default: 
       break;
  }
}
return valueStack.peek()

Lets start with infix expression -

2 * (3 + 5) - 6

On post fix conversion -

2 3 5 + * 6 -

Here is how we will proceed

Input token	Operation	Stack contents (top on the right)	Details
2	Push	2
3	Push	2, 3
4	Push	2, 3,5
+	Add	2,8	Pop two values: 3 and 5 and push the result 8.
*	Multiply	16	Pop two values: 2 and 8 and push the result 16.
6	Push	14, 6
-	Subtract	8	Pop two values: 14 and 6 and push result 8
(End of tokens)	Finish	8	Pop the only value 8 and return it

Java code
Here is code in java

   public int calculate(String s)  
   {  
     int n,r=0;  
     n=s.length();  
     Stack a=new Stack(n);  
     for(int i=0;i<n;i++)  
     {  
       char ch=s.charAt(i);  
       if(ch>='0'&&ch<='9')  
         a.push((int)(ch-'0'));  
       else  
       {  
         int x=a.pop();  
         int y=a.pop();  
         switch(ch)  
         {  
           case '+':r=x+y;  
              break;  
           case '-':r=y-x;  
              break;  
           case '*':r=x*y;  
              break;  
           case '/':r=y/x;  
              break;  
           default:r=0;  
         }  
         a.push(r);  
       }  
     }  
     r=a.pop();  
     return(r);  
   }  

Thanks.

References

• http://softwarecave.org/2014/04/03/evaluating-postfix-expressions/
• http://datastructure-using-java.blogspot.in/2010/02/write-java-program-to-evaluate-postfix.html