Write an Algorithm to convert an INFIX expression to a POSTFIX expression?

In infix expressions, the operator precedence is implicit unless we use parentheses. Therefore, for the infix to postfix conversion algorithm, we have to define the operator precedence inside the algorithm. We did this in the post covering infix, postfix and prefix expressions.

• What are infix, prefix and postfix expressions?

Important properties:-

• Let us consider the infix expression 2 + 3 * 4 and its postfix will be 2 3 4 * +. Notice that between infix and postfix the order of the numbers(or operands) is unchanged. It is 2 3 4 in both the cases. But the order of the operators * and + is affected in the two expressions.
• Only one stack is enough to convert an infix expression to postfix expression. The stack that we used in the algorithm will be used to change the order of operators form infix to postfix. The stack we use will only contain operators and open parentheses symbol ‘(‘. Postfix expressions do not contain parentheses. We shall not output the parentheses in the postfix output.

THE ALGORITHM:-

1. Create a stack
2. for each character ‘t’ in the input stream {
   • if (t is an operand)
     output t
   • else if (t is a right parentheses){
     POP and output tokens until a left parentheses is popped(but do not output)
     }
   • else {
     POP and output tokens until one of lower priority than t is encountered or a left parentheses is encountered
     or the stack is empty
     PUSH t
     }
3. POP and output tokens until the stack is empty.

For better understanding, let us trace out an example A * B – (C + D) + E

So our final POSTFIX Expression :- A B * C D + – E +