Evaluation of prefix expression using stack in Python

by

Evaluation of prefix expression using stack in Python

In prefix and postfix there are no brackets. In prefix expression evaluation we have to scan the string from right to left. If we encounter any operand then we will push it into the stack and if we encounter any operator then we will pop two elements from the stack and perform the operation using current operator and the result will get pushed in stack.

Steps for evaluating prefix expression.

  • 1. Accept the prefix expression as a string.
  • for I in string:
    if I is operand:
        Push it in stack
    else:
        Pop 2 elements from Stack
        Perform operations using current operator
        Push result back to stack
End for
  • 3. Pop the topmost element of the stack which is the result of the prefix expression.

Evaluate below prefix expression +-927

Accept above string in variable exp.

Read string from right to left.

evaluate prefix expression
Evaluate prefix expression using stack in python

CODE: Program to show use of stack to evaluate prefix expression using python.

"""
Author : ITVoyagers (itvoyagers.in)

Date :2nd November 2019

Description : Program to show use of stack to evaluate prefix expression using python.
"""
class evaluate_prefix:
    def __init__(self):
        self.items=[]
        self.size=-1
    def isEmpty(self):
        if(self.size==-1):
            return True
        else:
            return False
    def push(self,item):
        self.items.append(item)
        self.size+=1
    def pop(self):
        if self.isEmpty():
            return 0
        else:
            self.size-=1
            return self.items.pop()
    def seek(self):
        if self.isEmpty():
            return False
        else:
            return self.items[self.size]
    def evalute(self,expr):
        for i in reversed(expr):
            if i in '0123456789':
                self.push(i)
            else:
                op1=self.pop()
                op2=self.pop()
                result=self.cal(op1,op2,i)
                self.push(result)
        return self.pop()
    def cal(self,op1,op2,i):
        if i is '*':
            return int(op1)*int(op2)
        elif i is '/':
            return int(op1)/int(op2)
        elif i is '+':
            return int(op1)+int(op2)
        elif i is '-':
            return int(op1)-int(op2)
        elif i is '^':
            return int(op1)^int(op2)
s=evaluate_prefix()
expr=input('enter the prefix expression')
value=s.evalute(expr)
print('the result of postfix expression',expr,'is',value)

OUTPUT 
>>> ================================ RESTART ================================
>>> 
enter the prefix expression++596^-64
the result of postfix expression ++596^-64 is 20
>>> ================================ RESTART ================================
>>> 
enter the prefix expression+-927
the result of postfix expression +-927 is 14
>>> 
>>>

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

Leave a Comment