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 prefix expression and that is well known to computer, let's directly jump on to the algorithm.
- Reverse the expression.
- Tokenize the expression depending on the delemeter.
- Perform the following operations on each token.
- If token is operand, push the token to the stack
- If token is operator.
- Do two pops on stack. First one being operand 1 and second one being operand 2.
- Create an expression operand 1 + token + operand 2 and evaluate.
- Push the result in stack again.
- Pop the stack for the result.
Time Complexity : O(N^2)
Difference against the Post Fix Evaluation :
- We have to reverse in the first instance.
- In prefix evaluation we have to treat the first pop as operand 1 and second pop as operand 2 unlike post fix evaluation
Input Expression : + 1 * 2 3
Step 1 : + 1 * 2 3 => 3 2 * 1 +
Step 2 : Stack
Step 3 : Stack[3, 2]
Step 4 : Stack
Step 5 : Stack[6,1]
Step 5 : Stack - Result
Time Complexity : O(N)
You can fork the source code and unit tests from github.