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.

**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

**Algorithm Execution:**

**Input Expression :**+ 1 * 2 3

Step 1 : + 1 * 2 3 => 3 2 * 1 +

Step 2 : Stack[3]

Step 3 : Stack[3, 2]

Step 4 : Stack[6]

Step 5 : Stack[6,1]

Step 5 : Stack[7] - Result

**Time Complexity :**O(N)

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

why do we need to reverse ?

ReplyDelete