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?

by nikoo28
4 comments

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

4 comments

Hhhh July 30, 2017 - 17:26

Left or right parentheses?

Reply
nikoo28 July 31, 2017 - 06:26

Which parentheses are you talking about?

Reply
zulfi 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.

Reply
nikoo28 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.

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More