Infix to prefix conversion using Python

by

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

Leave a Comment