Using Python, Using Stacks: For this part of the assignment, you will write a fu

Question

Using Python, Using Stacks:

For this part of the assignment, you will write a function (calculateRPN) that uses a stack to calculate the result of an expression in Reverse Polish Notation (RPN) (also called Postfix notation).

Basically, for a binary operator (an operator that takes two arguments, called operands), the operands come first, then the operator. Operands can, themselves, be RPN expressions. One advantage to RPN is that no brackets are required to ensure proper order of operations. You can assume that the RPN expression contains only operators and numbers. The numbers, in our example, will be integers. Your function will take a single string as argument, and will return an integer (the result of the expression). You must support the following operators:

+: addition

-: subtraction

*: multiplication

/: division

The string argument will contain a RPN expression, with spaces between each number and/or operator. For example: 8 4 * 7 2 / + 4 1 + -

The statement above is equivalent to the following infix expression (and should compute to the value 30): ((8 * 4) + (7 / 2)) ­ (4 + 1) Some functions have been provided to help you to implement this function, since you may need to determine if a string contains a valid integer value, and it is does, you may wish to convert the string into an integer value. The following functions do exactly that:

def isInteger(str):    

for chr in str:       

if (chr < '0') or (chr > '9'):          

return False    

return True

def toInteger(str):   

return int(str)

You will use your implementation of Stack to compute the result.

The following is the basic algorithm you should use: for every token (value separated by spaces): if the token is a number: push the number to the stack if the token is an operator: Pop two numbers off of the stack (in reverse order) Apply the operator with the two numbers as operands Push the result to the stack The result is the only value left on the stack

Explanation / Answer

class Stack():

def __init__(self):

self.items = []

def isEmpty(self):

return self.items == []

def push(self, item):

return self.items.append(item)

def pop(self):

return self.items.pop()

def isInteger(str):

for chr in str:   

if (chr < '0') or (chr > '9'):

return False

return True

def toInteger(str):   

return int(str)

def postfix(str):

str=str.split()

nl=len(str)

#stack =[]

stack = Stack()

flag=isInteger(str)

for i in range(nl):

if str[i].isdigit():

stack.push(toInteger(str[i]))

elif str[i]=="+":

a=stack.pop()

b=stack.pop()

stack.push(toInteger(a)+toInteger(b))

elif str[i]=="*":

a=stack.pop()

b=stack.pop()

stack.push(toInteger(a)*toInteger(b))

elif str[i]=="/":

a=stack.pop()

b=stack.pop()

stack.push(toInteger(b)/toInteger(a))

elif str[i]=="-":

a=stack.pop()

b=stack.pop()

stack.push(toInteger(b)-toInteger(a))

return stack.pop()

s="10 2 8 * + 3 -"

result=postfix(s)

print(result)

===================================

Output:

23

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.