Infix to Postfix Conversion

 Algorithm for conversion of Infix to Postfix Notation

 

Step 1: Start 

Step 2: Start reading the infix expression from left to right. 

Step 3: Repeat Step 4 to 7 for each element until the Stack is empty. 

Step 4: If we scan a operand we output it, print it. 

Step 5: Else, 

             5.1: If the scanned operator is greater in precedence than the operator in the stack or if the stack is empty or the stack contains a "(", push it.

             5.2: Else,

                     Pop all the operators having greater or equal precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. In case there is a parenthesis while popping then stop and push the scanned operator in the stack. 

 Step 6: If a '(' is encountered, push it onto Stack. 

 Step 7: If a ')' is encountered, repeatedly pop from Stack and output it until a '(' is encountered 

Step 8: The output is printed in postfix notation 

Step 9: Stop.

 

 Example

Consider the following Infix Expression to be converted into Postfix Expression...

D = A + B * C

• Step 1 - The Operators in the given Infix Expression : = , + , *
• Step 2 - The Order of Operators according to their preference : * , + , =
• Step 3 - Now, convert the first operator * ----- D = A + B C *
• Step 4 - Convert the next operator + ----- D = A BC* +
• Step 5 - Convert the next operator = ----- D ABC*+ =

Finally, given Infix Expression is converted into Postfix Expression as follows...

D A B C * + =

 

 

Consider the following Infix Expression...

( A + B ) * ( C - D )

The given infix expression can be converted into postfix expression using Stack data Structure as follows...

 

 

The final Postfix Expression is as follows...

A B + C D - *