Scan the given expression from left to right and do the following for every scanned element. If the element is a number, push it into the stack If the element is an operator, pop operands for the operator from the stack. Evaluate the operator and push the result back to the stack ,The allowed operands are only single-digit operands. The program can be extended for multiple digits by adding a separator-like space between all elements (operators and operands) of the given expression. ,If the element is an operator, pop operands for the operator from the stack. Evaluate the operator and push the result back to the stack ,When the expression is ended, the number in the stack is the final answer
postfix evaluation: -4
757
2.
For i in post:
If i is an operand:
Push i in stack.
Else:
Pop two elements from stack e.g.X and Y
Perform operation with current operator on both the parents i.e X i Y
Push the result back into the stack.
End
for loop.2.
For i in post:
If i is an operand:
Push i in stack.
Else:
Pop two elements from stack e.g.X and Y
Perform operation with current operator on both the parents i.e X i Y
Push the result back into the stack.
End
for loop.CODE: Program to show use of stack to evaluate postfix expression using python.
""
"
Author: ITVoyagers(itvoyagers.in)
Date: 4 th November 2019
Description: Program to show use of stack to evaluate postfix expression using python.
""
"
class evaluate_postfix:
def __init__(self):
self.items = []
self.size = -1
def isEmpty(self):
return self.items == []
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 expr:
if i in '0123456789':
self.push(i)
else:
op1 = self.pop()
op2 = self.pop()
result = self.cal(op2, op1, i)
self.push(result)
return self.pop()
def cal(self, op2, op1, i):
if i is '*':
return int(op2) * int(op1)
elif i is '/':
return int(op2) / int(op1)
elif i is '+':
return int(op2) + int(op1)
elif i is '-':
return int(op2) - int(op1)
s = evaluate_postfix()
expr = input('enter the postfix expression')
value = s.evalute(expr)
print('the result of postfix expression', expr, 'is', value)>>> === === === === === === === === === === == 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 >>> >>>
A postfix expression (also known as Reverse Polish Notation) consists of a single letter or operator followed by two postfix strings. Every postfix string that is longer than a single variable has two operands followed by an operator.,Given a Postfix Expression, the task is to evaluate the given postfix Expression using a stack in Python.,Algebraic expressions are represented using the Postfix notation. Because parenthesis is not required in postfix notation, expressions written in postfix form are evaluated faster than expressions written in infix notation. We’ve talked about infix-to-postfix conversion. The evaluation of postfix expressions is described in this post.,If the operator is ‘/’ then perform a division operation on the top two elements by popping them out.
Output:
The value of the given postfix expression = 9
Input:
given postfix Expression = "72/96-8+"Below is the implementation:
# Function which accepts the given postfix expression as argument
# and evaluates the expression using stack and
return the value
def evaluatePostfix(givenExp):
# Create a stack by taking an empty list which acts
# as a stack in this
case to hold operands(or values).
givenstack = []
# Traverse the given postfix expression using For loop.
for charact in givenExp:
# Push the element into the given stack
if it is a number.
if charact.isdigit():
givenstack.append(int(charact))
#
if the character is operator
else:
# remove the top two elements from the stack
topfirst = givenstack.pop()
topsecond = givenstack.pop()
# Evaluate the operator and
return the answer to the stack using append() funtion.
# If the operator is '+'
then perform an addition operation on
# the top two elements by popping them out.
if charact == '+':
givenstack.append(topsecond + topfirst)
# If the operator is '-'
then perform a subtraction operation
# on the top two elements by popping them out.
elif charact == '-':
givenstack.append(topsecond - topfirst)
# If the operator is '/'
then perform a division operation on
# the top two elements by popping them out.
elif charact == '×':
givenstack.append(topsecond * topfirst)
# If the operator is '*'
then perform a multiplication operation
# on the top two elements by popping them out.
elif charact == '/':
givenstack.append(topsecond // topfirst)
# The only number in the stack is the final answer when the expression is traversed.#
return the answer to the main
function
return givenstack.pop()
# Driver code # Give the postfix Expression as static input and store it in a variable.givenExp = "91-82×63+"
# Pass the given postfix Expression as an argument to evalpostfix
function print('The value of the given postfix expression =', evaluatePostfix(givenExp))Time complexity of evaluation algorithm is O(n) where n is number of characters in input expression.,Below is the implementation of above algorithm.
postfix evaluation: -4