Infix to postfix conversion using Python

Infix to postfix( infix-to-postfix ) conversion using Python

In infix expression there are operators, operands and brackets but when it comes to postfix expressions it doesn’t have any brackets in it. We have to take care of one thing and that is precedence of operators. Higher order * / Lower order + – During the evaluation we have to evaluate higher order operators first and if we encounter two operators with same precedence then we will evaluate both of them from left to right which means in below example we will evaluate X+Y first X+Y-Z

Stack has many Real Time Applications

• 1. Expression evaluation and syntax parsing
• 2. Backtracking: The prototypical example of a backtracking algorithm is depth-first search, which finds all vertices of a graph that can be reached from a specified starting vertex
• 3. Books kept one above another.
• 4. Matching parenthesis by compiler.
• 5. To reverse a word
• 6. An “undo” mechanism in text editors.
• 7. Stack of books
• 8. Pushdown Automata
• 9. Memory Management
• 10. Evaluating prefix, postfix and infix expressions.

Steps for converting infix expression into postfix expression.

1.	Accept infix expression as a string inxexp.

2.	For i in inxexp:
    If i is alphabet or digit:
        Append it to the postfix expression
    Else if i is '(':
        Push '(' in the stack
    Else if i is ')':
        Pop the element from the stack and append it postfix expression until we get ')' on top of      the stack.
        Pop '(' from the stack and don't add it in postfix expression.
    Else if i is in '*/+-‘:
        If stack is empty or top of the stack is '(':
            Push the operator in the stack.
        Else:
            Pop the elements from the stack and continue this until the operator on the top of the stack has same or less residence then the i.
    Else:
        Push i in stack.


3. Once we scanned inxexp completely, start popping the elements from the stack and appending them to postfix expression. 
And if we encounter '(' discard it.

CODE: Program to show use of stack in infix to postfix conversion using python

"""
Author : ITVoyagers (itvoyagers.in)

Date :31st October 2019

Description : Program to show use of stack in infix to postfix conversion using python.
"""
class infix_to_postfix:
    precedence={'^':5,'*':4,'/':4,'+':3,'-':3,'(':2,')':1}
    def __init__(self):
        self.items=[]
        self.size=-1
    def push(self,value):
        self.items.append(value)
        self.size+=1
    def pop(self):
        if self.isempty():
            return 0
        else:
            self.size-=1
            return self.items.pop()
    def isempty(self):
        if(self.size==-1):
            return True
        else:
            return False
    def seek(self):
        if self.isempty():
            return false
        else:
            return self.items[self.size]
    def isOperand(self,i):
        if i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
            return True
        else:
            return False
    def infixtopostfix (self,expr):
        postfix=""
        print('postfix expression after every iteration is:')
        for i in expr:
            if(len(expr)%2==0):
                print("Incorrect infix expr")
                return False
            elif(self.isOperand(i)):
                postfix +=i
            elif(i in '+-*/^'):
                while(len(self.items)and self.precedence[i]<=self.precedence[self.seek()]):
                    postfix+=self.pop()
                self.push(i)
            elif i is '(':
                self.push(i)
            elif i is ')':
                o=self.pop()
                while o!='(':
                    postfix +=o
                    o=self.pop()
            print(postfix)
                #end of for
        while len(self.items):
            if(self.seek()=='('):
                self.pop()
            else:
                postfix+=self.pop()
        return postfix
s=infix_to_postfix()
expr=input('enter the expression ')
result=s.infixtopostfix(expr)
if (result!=False):
    print("the postfix expr of :",expr,"is",result)

OUTPUT

enter the expression G+A+(U-R)^I
postfix expression after every iteration is:
G
G
GA
GA+
GA+
GA+U
GA+U
GA+UR
GA+UR-
GA+UR-
GA+UR-I
the postfix expr of : G+A+(U-R)^I is GA+UR-I^+
>>> 

Note : Please note that above program is compatible with Python 3 or higher version.

You can also check following content on conversion, evaluation and other applications of stack

• Stack to reverse string using python
• Infix to Prefix expression using stack in Python
• Check order of parentheses with stack