Reverse Polish Notation (RPN), also known as postfix notation, is an alternate w

Question

Reverse Polish Notation (RPN), also known as postfix notation, is an alternate way to represent a sequence of arithmetic operations. In RPN, we write the operands/values first, followed by the applicable arithmetic operator (for example, 5 + 2 would be written as 52+). To evaluate a postfix/RPN expression, we record (save) operands until we reach an operator. Once we see an operator, we apply it to the last two operands we saw (in the appropriate order) and then record the result while we continue scanning for operands and operators. When we are done, we should have exactly one recorded value left, which will be our final answer.

For example, consider the expression 43*5– (assume that each operand is initially one digit in length). We begin by storing 4 and 3. When we encounter the multiplication operator, we multiply our last two stored values (4 and 3) and record the result (12). We record the next operand (5). Finally, we encounter the subtraction operator, so we perform 12–5 from our stored values to get the final answer of 7. Here is how the list would evolve over time:

In Python, we can perform this calculation using a list. Each time we read an operand, we use append() to add it to the end of our (initially empty) list. Each time we read an operator, we use pop() to remove and store the last two elements of the list in temporary variables. We apply the operator, and then append the result to the end of the list. When we are done, if the list contains exactly one value, that value is our final answer. If it does not, then there must have been an error in the original input value.

Complete the rpn() function, which takes a string representing an RPN expression (with single-digit operands) as its only argument. The function returns the numerical value of the original expression (as an integer). You may assume that the input string is properly formatted.

Note: Since we are working exclusively with integer values for this problem, interpret any division operators as performing floor (integer) division. Thus 83/ would evaluate to 2, not 2.67.

Examples:

Explanation / Answer

//==================== rpn.py ===================================//

def rpn(s):
   l= len(s)
   stack = []
   for i in range(0,l):
       if(s[i]=='+'):
           a=int(stack.pop())
           b=int(stack.pop())
           c=a+b
           stack.append(c)
       elif(s[i]=='-'):
           a=int(stack.pop())
           b=int(stack.pop())
           c=b-a
           stack.append(c)
       elif(s[i]=='*'):
           a=int(stack.pop())
           b=int(stack.pop())
           c=b*a
           stack.append(c)
       elif(s[i]=='/'):
           a=int(stack.pop())
           b=int(stack.pop())
           c=b/a
           stack.append(c)
       else:
           stack.append(int(s[i]))
      
   return int(stack.pop())

def main():  
   print('Testing rpn() for "532*+": ' + str(rpn('532*+')))
   print('Testing rpn() for "94/12+-": ' + str(rpn('94/12+-')))
   print('Testing rpn() for "12+3*6+23+/": ' + str(rpn('12+3*6+23+/')))
   print('Testing rpn() for "94+1-95/*728/--": ' + str(rpn('94+1-95/*728/--')))
  
main()

//==================== OUTPUT ===================================//

Testing rpn() for "532*+": 11
Testing rpn() for "94/12+-": -1
Testing rpn() for "12+3*6+23+/": 3
Testing rpn() for "94+1-95/*728/--": 5

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

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