INFIX TO POSTFIX CONVERSION USING STACK














































INFIX TO POSTFIX CONVERSION USING STACK



Infix to postfix conversion using stack



Infix expression:

An infix expression can be represented as: <operand><operator><operand>.

Operator is preceded and succeeded by an operand eg: X+Y.


Postfix expression:

A postfix expression can be represented as: <operand><operand><operator>.

Operator is succeeded by operands eg: XY+.


Priority order:

Following is the list of lowest to highest  priority of operators:

Priority 1 ->'' + '', '' - ''

Priority 2 -> '' * '', '' / ''

Priority 3 -> '' ^ ''


Rules:

  1. Start by inserting '' ( '' in the stack

  2. If character == operand, put in postfix expression

  3. If character == operator, put in stack

  4. If scanned operator priority (eg  '' * '') > top operator priority (eg '' + ''), push in stack

  5. If scanned operator priority (eg '' + '') < top operator priority (eg '' * ''), pop till priority[scanned] becomes > priority[top]

  6. If '' ) '' ,  encountered, pop till '' ( ''




Example:


Infix expression = (A+(C+D*F+T*A)*B/C)



Scanned 

character

              Stack

Postfix 

expression

(

(


A

(

A

+

(+

A

(

(+(

A

C

(+(

AC

+

(+(+

AC

D

(+(+

ACD

*

(+(+*

ACD

F

(+(+*

ACDF

+

(+(+

ACDF*+

T

(+(+

ACDF*+T

*

(+(+*

ACDF*+T

A

(+(+*

ACDF*+TA

)

(+

ACDF*+TA*+

*

(+*

ACDF*+TA*+

B

(+*

ACDF*+TA*+B

/

(+/

ACDF*+TA*+B

C


(+/


ACDF*+TA*+B*C

)

EMPTY

ACDF*+TA*+B*C/+


Program:


OPERATORS = set(['+', '-', '*', '/', '(', ')', '^'])  # set of operators

 PRIORITY = {'+':1, '-':1, '*':2, '/':2, '^':3} # dictionary having priorities 

 

def infix_to_postfix(expression): #input expression

    stack = [] # initially stack empty

    output = '' # initially output empty

    

    for ch in expression:

        if ch not in OPERATORS:  # if an operand then put it directly in postfix expression

            output+= ch

        elif ch=='(':  # else operators should be put in stack

            stack.append('(')

        elif ch==')':

            while stack and stack[-1]!= '(':

                output+=stack.pop()

            stack.pop()

        else:

            # lesser priority can't be on top on higher or equal priority    

             # so pop and put in output   

            while stack and stack[-1]!='(' and PRIORITY[ch]<=PRIORITY[stack[-1]]:

                output+=stack.pop()

            stack.append(ch)

    while stack:

output+=stack.pop()

return output

 

expression = input('Enter infix expression')

print('infix expression: ',expression)

print('postfix expression: ',infix_to_postfix(expression))


Output:






Comments