Write an algorithm to convert infix expression into postfix expression with example.

Step 1: Push “(” onto stack, and add “)” to the end of P.

Step 2: Scan P from left to right and repeat steps 3 to 6 for each element of P until the stack is empty.

Step 3: If an operand is encountered, add it to postfix operation.

Step 4: If a left parenthesis is encountered, push it onto stack.

Step 5: If an operator is encountered, then

  1. Repeatedly pop from the stack and each operator (on the top of stack), which has the same precedence as, or higher precedence than operator.
  2. Add operator to stack.

Step 6: If a right parenthesis is encountered, then

  1. Repeatedly pop from stack and add to postfix string.
  2. Remove the left parenthesis.

Step 7: Exit.

Character scanned

Stack

Postfix expression (Q)

A

+

(

B

/

C

-

(

D

*

E

^

F

)

+

G

)

*

H

)

   (

   ( +

   ( + (

   ( + (

   ( + ( /

   ( + ( /

   ( + ( -

   ( + ( - (

   ( + ( - (

   ( + ( - ( *

   ( + ( - ( *

   ( + ( - ( * ^

   ( + ( - ( * ^

   ( + ( -

   ( + ( +

   ( + ( +

   ( +

   ( + *

   ( + *

A

A

A

A B

A B

A B C

A B C /

A B C /

A B C / D

A B C / D

A B C / D E

A B C / D E

A B C / D E F

A B C / D E F ^ *

A B C / D E F ^ * -

A B C / D E F ^ * - G

A B C / D E F ^ * - G +

A B C / D E F ^ * - G +

A B C / D E F ^ * - G + H

A B C / D E F ^ * - G + H * +

Share with

Comments 0

Add your comment