Evaluating a Postfix Expression

Introduction:

• Postfix expressions are parenthesis free notation and precedence is already defined so evaluation is done very easily.
• Example of Postfix expression are

1. AB+C*
2. 234*+5- 

Algorithm for Postfix evaluation:

1. Read the tokens from the postfix string one at a time from left to right
2. Initialize an empty stack
3. If the token is an operand, push the operand in to the stack
4. If the token is an operator,then there will be at least 2 operands in the stack.Pop the top 2 elements from the stack and apply the operator to the poped out 2 elements.The result of this operation is push back in to the stack.
5. After all the characters are read,only one element is present in the stack that is the result  

Example for Postfix Evaluation:

Example1:
Postfix expression-->234*+5- 
Solution: 

1. Initially the stack is empty.
2. Read the token 2. 2 is an operand.Push 2 in to the stack. now stack->2
3. Read the token 3.3 is an operand. Push 3 in to the stack. now stack->32
4. Read the token 4.4 is an operand. Push 4 in to the stack. now stack->432 
5. Read the token *.* is an operator. pop the top 2 elements 4,3 from the stack and 4*3=12.then push 12 in to the stack. now stack->12 2 
6. Read the token +.+is an operator.pop the 2 elements 12,2 from the stack and 12+2=12.then push 12 in to the stack. now stack->14
7. Read the token 5.5 is an operand.Push 5 in to the stack. now stack->5 14
8. Read the token -.- is an operator.pop the 2 elements 14,5 from the stack and 14-5=9.then push 9 in to the stack. now stack->9
9. result=9  

The value for 234*+5- is 9 

Exercise for Postfix Evaluation: 

1. 234+56**+
2. 623+-382/+*