Evaluate Post Fix Expression

We have already written algorithm to convert infix expression to post fix expression. You can refer my previous post for the same. As we have already having a post fix expression and that is well known to computer, let's directly jump on to the algorithm.

Algorithm:

1. Tokenize the expression depending on the delemeter.
2. Perform the following operations on each token.
1. If token is operand, push the token to the stack
2. If token is operator.
1. Do two pops on stack. First one being operand 2 and second one being operand 1.
2. Create an expression operand 1 + token + operand 2 and evaluate. 
3. Push the result in stack again.
3. Pop the stack for the result.

Time Complexity : O(N)

Algorithm Execution:

Input Expression : 1 2 3 * +

Step 1 : Stack[1]

Step 3 : Stack[1, 2]

Step 4 : Stack[1,2,3]

Step 5 : Stack[1,6]

Step 5 : Stack[7] - Result

You can fork the source code and unit tests from github.