Reverse Polish Notation (RPN) Calculator in Python





5.00/5 (2 votes)
How to create a Reverse Polish Notation (RPN) Calculator using Python
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
- 10th November, 2022: Initial version