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

# 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.

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

 INPUT CHARACTER OPERATION ON STACK STACK POSTFIX EXPRESSION A Empty A * Push * A B * A B – Check and Push – A B * ( Push – ( A B * C – ( A B * C + Check and Push – ( + A B * C D – ( + A B * C D ) Pop and append to postfix till ‘(‘ – A B * C D + + Check and push + A B * C D + – E + A B * C D + – E End of Input Pop till Empty Empty A B * C D + – E +

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

#### You may also like

July 30, 2017 - 17:26

Left or right parentheses?

July 31, 2017 - 06:26

Which parentheses are you talking about?

March 6, 2017 - 09:39

“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”

In your example when a left parentheses occurs, you have just pushed it on the stack and did not pop ‘-‘ character which is in the stack. This is not in accordance with your algorithm Plz specify clearly what to do when a left parentheses occurs???

Zulfi.

March 8, 2017 - 12:36

Hi Zulfi,

Can you describe in a little detail, which part are you unable to understand. The table lists all the rules.