- Postfix expressions are parenthesis free notation and precedence is already defined so evaluation is done very easily.
- Example of Postfix expression are
- Read the tokens from the postfix string one at a time from left to right
- Initialize an empty stack
- If the token is an operand, push the operand in to the stack
- 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.
- After all the characters are read,only one element is present in the stack that is the result
- Initially the stack is empty.
- Read the token 2. 2 is an operand.Push 2 in to the stack. now stack->2
- Read the token 3.3 is an operand. Push 3 in to the stack. now stack->32
- Read the token 4.4 is an operand. Push 4 in to the stack. now stack->432
- 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
- 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
- Read the token 5.5 is an operand.Push 5 in to the stack. now stack->5 14
- 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
Exercise for Postfix Evaluation: