Infix to Post Fix

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's solve the problem using computer language and we are going to take the help of the stack to solve this problem. Why we opted for a stack ADT? Good question and I believe, the next explanation will clarify your answer. So let's not jump on that question now. 

Given Infix Expression : A + B * C

We are going to use the following use the following components for the algorithm.

1. Stack
2. String

Algorithm :

1. Tokenize the expression depending on the delemeter.
2. Perform the steps for each of the token
1. If token is an operand append to the result string
2. If token is an operator peek the stack, check if operator and check for the operator precedence
1. pop the stack till stack has operator precedence greater than equal to token precedence and append that to string.
2. else push the operator to the stack
3. If you find an open parenthesis, push that to the stack.
4. If you find an closed parenthesis, pop and append to the string till you get a open parenthesis. Then pop the open parenthesis too.
3. Pop the entire stack and append that to result string.

Time Complexity : O(n+m)) + O(m) where n =  no of tokens, m = stack size

Execution of algorithm:

Step 1 : String : A :: Stack : []

Step 2 : String : A :: Stack : [+]

Step 3 : String : AB :: Stack : [+]

Step 4 : String : AB :: Stack : [+, *]

Step 5 : String : ABC :: Stack : [+,*]

Step 6 : String : ABC*+ :: Stack : []

I took a very easy expression to keep the post simple and more understandable. You can apply the same algorithm to process your complex expressions. Now it's time to convert this algorithm steps to a program. I am using java to do so.

The complete program with github can be forked here