Algorithm to convert infix expression to postfix form

The following algorithm transforms the infix expression X into its equivalent postfix expression Y. The algorithm uses a stack to temporarily hold operators and left parentheses. The postfix expression Y will be constructed from left to right using the operands from X and the operators which are removed from STACK.

We begin by pushing a left parenthesis onto STACK and adding a right parenthesis at the end of X. The algorithm is completed when STACK is empty.

Algorithm

Suppose X is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression Y.

1. push "(" onto stack, and add ")" to the end of X.

2. scan X from left to right and repeat Steps 3 to 6 for each element of X until the STACK is empty :

3. if an operand is encountered, add it to Y.

4. if a left parenthesis is encountered, push it onto STACK.

5. if an operator is encountered, then
(a) Repeatedly pop from STACK and add to Y each operator (on the top of STACK) which has the same precedence as or higher precedence than operator.
(b) Add operator to STACK.
/*End of If structure */

6. if a right parenthesis is encountered, then :
(a) Repeatedly pop from STACK and add to Y each operator (on the top of STACK) until a left parenthesis is encountered.
(b) Remove the left parenthesis. [Do not add the left parenthesis to Y].
/* end of If structure */
/* end of Step 2 loop */

7. exit.

This is an Algorithm to Convert Infix expression to Postfix. If you have any questions then comment below.

Leave a Comment