Reverse Polish Notation (RPN) Calculator in Python

• Download rpn.zip - 741 B

Introduction

Through this article, I wish to demonstrate creating a Reverse Polish Notation (RPN) Calculator which can be used to evaluate postfix expressions. In a postfix operation, an operator appears after its operands. For example, an infix expression like 25 + 12 would be written as 25 12 + in the postfix notation. A postfix expression is evaluated in the order in which the operations appear (left to right).

For this, we need to define a stack class. This stack class will be the container for the operands as well as intermediate results. The final result also gets stored in the stack and is extracted at the end of the process and displayed.

Background

RPN Calculator, also known as Stack Calculator, is a special type of calculator in which there must be two operands before an operator in an expression. The RPN calculator works by pushing operands into a stack until an operator is encountered. When an operator is encountered, the last two pushed operands are popped, the required operation is performed, and the result of the operation is again pushed into the stack. At the end of the expression, the last value is popped from the stack and displayed as the final result.

Using the Code

Following is the code for the Node class which is the building block for our Stack class. It defines a constructor and the required getter and setter methods.

# Representing the node for the stack.
# The node class defines a constructor and the required getter and setter methods.

class Node:

   def __init__(self,d):
       self.data = d

   def setnext(self,n):
       self.next = n

   def getdata(self):
       return self.data

   def getnext(self):
       return self.next

Following is the code for the Stack class. It defines a constructor and the push and pop operations in addition to a method to check if the stack is empty.

# Representing the stack class.
# The stack class defines a constructor and the implementations for the
# push and pop operations. It also contains a method to check if the stack is empty.

class Stack:

   def __init__(self):
       self.top = None

   def push(self,d):
       self.newnode = Node(d)
       self.newnode.setnext(self.top)
       self.top = self.newnode

   def pop(self):
       temp = self.top
       self.top = self.top.getnext()
       n = temp.getdata()
       del temp
       return n

   def isempty(self):
       return self.top == None

Following is the code for the main program. The main program involves accepting input from the user and performing the calculations by using the functions of our stack class. The expression entered to be evaluated must have a space between two operands as well as between an operand and operator, for example, 78 100 + 200 - 5 *

The code uses the sub() function of the regular expression module (re) to subsitute multiple spaces in the postfix expression with one space and the split() function to parse the expression and extract the elements of the expression (operators and operands) into a list. The strip() function is used to remove the leading and trailing spaces. It pushes the operands into the stack and pops the last two operands and pushes their result when an operator is encountered. At the end, it pops and displays the value from the stack as the final result.

import re

if __name__ == "__main__":
    try:
        mystack = Stack()
        expr = input("Enter expression with space between numbers and operators: ")
        expr = re.sub(" +"," ",expr)
        expr = expr.strip()
        elements = re.split(r"[\s]",expr)
        for x in elements:
            if x == "+":
                n1 = int(mystack.pop())
                n2 = int(mystack.pop())
                n3 = n2 + n1
                mystack.push(n3)
            elif x == "-":
                n1 = int(mystack.pop())
                n2 = int(mystack.pop())
                n3 = n2 - n1
                mystack.push(n3)
            elif x == "*":
                n1 = int(mystack.pop())
                n2 = int(mystack.pop())
                n3 = n2 * n1
                mystack.push(n3)
            elif x == "//":
                n1 = int(mystack.pop())
                n2 = int(mystack.pop())
                n3 = n2 // n1
                mystack.push(n3)
            elif x == "/":
                n1 = int(mystack.pop())
                n2 = int(mystack.pop())
                n3 = n2 / n1
                mystack.push(n3)
            else:
                mystack.push(x)
        print("Result: " + str(mystack.pop()))
    except AttributeError as e:
        print("Invalid Expression: " + str(e))

History

• 10^th November, 2022: Initial version