Infix to Prefix

In my previous post we evaluated the algorithm to convert a prefix expression to post fix expression. Infix to Post fix algorithm is going to be handy for writing the algorithm of Infix to Prefix. We just need few additional steps to do so. But before jumping on to the solution for computer program, let's first solve it in a mathematical way. 

Before just jumping on to the algorithm and implementation, let's start slow. I am going to convert a infix expression first in a traditional mathematical way and then will derive the algorithm using computer language. Let me start with a simple example.

Order Of Operation

1. Parenthesis - ( ) { } [ ]
2. Exponent (Right to left)
3. Multiplication and Division (Left to Right)
4. Addition and Subtraction (Left to Right)

Given Infix Expression : A + B * C

Steps:

1. First manually put the parenthesis depending on the operator precedence.
2. Then start evaluating from the inner most expression.
3. Remove the parenthesis.

A + B * C -> A + ( B * C ) -> A + ( * B  C ) -> + A ( * B C )  + -> + A * B C

Final Result : + A * B C

Now let directly jump on to the computer algorithm. I will not be writing the infix to post fix algorithm here. Please refer my previous post for the same.

Algorithm:

1. Reverse the input expression
2. Change all open parenthesis to close and visa versa. 
3. Run the infix to post fix algorithm
4. Reverse the output

Time Complexity : 

Time Complexity of infix to post fix + O(n) + O(n) + O(n)

=>(O(n+m)) + O(m)) + O(n) + O(n) + O(n) where n =  no of tokens, m = stack size

You can also fork the code from github.