Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Algorithm for converting infix expression to postfix expression form

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 431
    Comment on it

    An algorithm to convert infix expression into a postfix expression using “Stack”. The purpose of stack is to reverse the order of the operators in the expression as it is used to hold operators rather than numbers.

     

    POSTFIX (N, M)
    Let us assume that N is the arithmetic expression written in an infix notation. This algorithm will find the equivalent postfix expression M.
    1. Push (  onto STACK, and add ) to the end of N.
    2. Scan N from left to right and repeat steps 3 to 6 for each element of N until the STACK is empty.
    3. If an operand is encountered, add it to M.
    4. If a left parenthesis is encountered, push it onto STACK.
    5. If an operator (*) is encountered, then:
    (a) Add (*) to STACK. [End of if structure].
    (b) Repeatedly pop from STACK and add M each operator (on the top of STACK) which has the same precedence or higher precedence than (*).
    6. If a right parenthesis is encountered, then:
    (a) Repeatedly pop from STACK and add to M each operator (on the top of STACK) until a left parenthesis is encountered.
    (b) Remove the left parenthesis. [End of if structure].
    [End of loop in step 2].
    7. Exit.

     

    Example 1: X * Y + Z is in infix notation form after applying an algorithm its equivalent postfix notation will be X Y * Z +

    S. No Current symbol stack operator postfix string
    1 X   X
    2 * * X
    3 Y * X Y
    4 + + X Y *

    {* has higher precedence than +}

    5 Z + X Y * Z
    6     X Y * Z +

    Firstly, the operands are printed when it is read. Next an operator is pushed onto the stack if it is empty. If the operator on the top of the stack has higher precedence than the one being read, pop and print the one on top and then push the new operator on. At the end of the expression, pop the operators on the stack one at a time and then print them.

     

    Example 2: M *( Q + W) becomes M Q W + *

    S. No. Current symbol stack operator postfix string
    1 M   M
    2 * * M
    3 ( * ( M
    4 Q * ( M Q
    5 + * ( + M Q
    6 W * ( + M Q W
    7 ) *

    M Q W+

    8     M Q W + *

    An expression in parenthesis must be done first. Here “(“ was pushed to the operator stack as to provide a marker. The stack was treated as empty and the next operator “+” was pushed on. Then when the right parenthesis is read, the stack is popped until the corresponding left parenthesis is found.

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: