How to Convert Infix expression to Postfix expression

Infix expression is an expression which is quickly readable and understandable for humans. The operators are fixed in between two of its operands in the infix expression. On the other hand, the operator appears after the two operands in the postfix expression.

A+B is infix

AB+ is postfix

The operators are +, — , *, /, ^. The infix expression can also contain round brackets as open bracket ( and closed bracket ).

Math symbols

The infix expression can be converted to postfix expression based on the precedence of the operators. The order of precedence is as below:

Operator precedence table

So, is it hard to understand?!!

Definitely NO ✅

The conditions to convert infix expression to a postfix expression is pretty simple.

Conditions to follow to convert infix expression to postfix expression:

• If the incoming character is an operand, append the incoming character to the postfix expression. Do not push incoming operand into stack.
• If the incoming character is an open bracket (, push into stack.
• If the stack is empty, and if the incoming symbol is an operator, push the operator into the stack.
• If the stack has an open bracket ( on the top of the stack, and if the incoming symbol is an operator, push the operator into the stack.
• If the incoming symbol is a closed bracket ) , then pop the elements from the top of stack and append them to postfix expression continuously till the stack top has an open bracket. Finally pop the open bracket from the stack top.
• If the incoming symbol is a higher precedence operator than the lower precedence operator at the top of the stack, push the incoming higher precedence operator into the stack.
• If the incoming symbol is a lower precedence operator and the top of stack has a higher precedence operator, pop the higher precedence operator from the stack and append it to the postfix expression. Then again test the conditions of the incoming lower precedence operator with the element at top of stack.
• If the incoming operator has equal precedence with the operator at the top of the stack, pop and append the the operator at the top of stack to postfix expression. Then push the incoming operator into the stack.
• At the end of the infix expression, pop every element from the top of the stack and append to the end of postfix expression.

Converting Infix expression to Postfix expression:

Let us see an example below to make it more clear. We can convert using a stack data structure. We are going to scan every character in the infix expression from left side to right side and push and pop from stack based on the conditions above. Convert the infix expression below to postfix:

K+L-M*N+(O^P)*W/U/V+H^A^Q

Now all characters in the infix expression has been checked. But the stack is not empty at the last row in the table. Pop all operators in the stack from the top and append it to the postfix expression.

Popping remaining operators from the stack top and appending to postfix expression

On doing that, the stack becomes empty. The postfix expression becomes

KL+MN*-OP^W*U/V/+HA^Q^+

Now the infix expression is converted to postfix expression using Stack data structure.

Code snippet in Python to convert Infix to Postfix expression:

Time complexity: O(N) where N is the length of given infix expression string.

Space complexity: O(N) where N is the length of given infix expression string. O(N) is because a stack data structure is used.

Thanks for reading my article!