Infix to prefix( infix-to-prefix) conversion using Python
For us infix notation is more suitable but this is not the case with systems because of operator precedence.
System uses postfix or prefix notations to solve the equation.
This is when stack comes into the picture. Using stack, system can easily execute the equation with prefix or postfix notations.
X+Y infix
+XY prefix
An infix expression encounters four symbols
Open bracket
Close bracket
Operand which can be alphanumeric
Operator
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 prefix expression.
- 1. Accept infix expression string as a input.
- 2. Reverse the infix expression string
- 3. Now reverse each bracket. If you encountered any open bracket ‘(‘ reverse it and make it close bracket ‘)’. And vice versa
- 4. Convert the reverse string into the postfix expression and if during conversion you find any operator then we have to check its precedence with the one in stack.
- 5. If precedence of current operator is higher than the one in stack then push the current operator into the stack else pop the operator from the stack.
- 6. Finally reverse the postfix expression.
CODE: Program to show use of stack in infix to prefix conversion using python
""" Author : ITVoyagers (itvoyagers.in) Date :1st November 2019 Description : Program to show use of stack in infix to prefix conversion using python. """ class infix_to_prefix: 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 is0perand(self,i): if i.isalpha() or i in '1234567890': return True else: return False def reverse(self,expr): rev="" for i in expr: if i is '(': i=')' elif i is ')': i='(' rev=i+rev return rev def infixtoprefix (self,expr): prefix="" print('prefix expression after every iteration is:') for i in expr: if(len(expr)%2==0): print("Incorrect infix expr") return False elif(self.is0perand(i)): prefix +=i elif(i in '+-*/^'): while(len(self.items)and self.precedence[i] < self.precedence[self.seek()]): prefix+=self.pop() self.push(i) elif i is '(': self.push(i) elif i is ')': o=self.pop() while o!='(': prefix +=o o=self.pop() print(prefix) #end of for while len(self.items): if(self.seek()=='('): self.pop() else: prefix+=self.pop() print(prefix) return prefix s=infix_to_prefix() expr=input('enter the expression ') rev="" rev=s.reverse(expr) #print(rev) result=s.infixtoprefix(rev) if (result!=False): prefix=s.reverse(result) print("the prefix expr of :",expr,"is",prefix)
OUTPUT
>>> enter the expression G+A+(U-R)^I prefix expression after every iteration is: I I I IR IR IRU IRU- IRU-^ IRU-^A IRU-^A IRU-^AG IRU-^AG+ IRU-^AG++ the prefix expr of : G+A+(U-R)^I is ++GA^-URI >>>
You can also check following content on conversion, evaluation and other applications of stack
- Infix to Postfix expression using stack in Python
- Stack to reverse string using python
- Check order of parentheses with stack