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
do it for numerical expressions
like for example
23+55 gives output as [23,55,’+’]
23*55-12 gives output as [23,55,’*’,12,’-‘]
23+55*12 gives output as [23,55,12,’*’,’+’]