Skip to content

Instantly share code, notes, and snippets.

@JoseALermaIII
Last active June 30, 2019 11:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save JoseALermaIII/feea6ffa79c730b253a48a587cb78b6c to your computer and use it in GitHub Desktop.
Save JoseALermaIII/feea6ffa79c730b253a48a587cb78b6c to your computer and use it in GitHub Desktop.
Reverse Polish Notation Calculator
#!/usr/bin/env python
#
# RPNcalc.py
#
# https://JoseALerma.com/posts/2017/Aug/15/rpn-calculator/
# Our task is to create an RPN Calculator function in Python assuming all
# numbers are single digits, the input will already be in RPN, and a First In
# Last Out stack is used. Bonus if you can make a function to convert infix
# notation (including parenthesis) to RPN (expect to be assigned this next time).
#
from re import compile
def infix_to_postfix(string):
precedence = {'*': 2, '/': 2, '+': 1, '-': 1, '(': 0}
stack = []
output = []
oper_count, paren_count = 0, 0
# Test infix equation for compatibility
for element in string:
try:
# print(element, oper_count, paren_count) # Debug
if oper_count == 2:
raise Exception("Multi-digit operand")
elif element.isdigit():
oper_count += 1
elif element in "+-*/":
oper_count = 0
elif element == '(':
paren_count += 1
elif element == ')':
paren_count -= 1
else:
raise Exception("Invalid operation")
except Exception as instance:
print(instance, "\nString:", string, "\nElement: ", element)
raise
try:
if paren_count != 0:
raise Exception("Mismatched parenthesis")
elif compile(r"[+\-*/]{2,}").search(string) is not None:
raise Exception("Sequential operations")
except Exception as instance:
print(instance, "\n String:", string, "\nElement: ", element)
raise
for element in string:
if element.isdigit():
output.append(element)
elif element == '(':
stack.append(element)
elif element == ')':
top_element = stack.pop()
while top_element != '(':
output.append(top_element)
top_element = stack.pop()
else:
while (len(stack) != 0) and (precedence[stack[len(stack) - 1]] >= precedence[element]):
output.append(stack.pop())
stack.append(element)
# Debug
# print("String:", string, '\n'
# "Element:", element, '\n'
# "Stack:", stack, '\n'
# "Output:", output, '\n')
while len(stack) != 0:
output.append(stack.pop())
return ''.join(output)
def postfix_calculator(string):
stack = []
oper1, oper2 = '', ''
oper_count = 0
# Test RPN equation for compatibility
for element in string:
try:
# print(element, oper_count) # Debug
if oper_count == 3:
raise Exception("Multi-digit operand")
elif element.isdigit():
oper_count += 1
elif element in "+-*/":
oper_count = 0
else:
raise Exception("Invalid operation")
except Exception as instance:
print(instance, "\nString:", string, "\nElement: ", element)
raise
for element in string:
if element in "+-*/":
oper1 = stack.pop()
oper2 = stack.pop()
if element == '+':
stack.append(oper1 + oper2)
elif element == '-':
stack.append(oper2 - oper1)
elif element == '*':
stack.append(oper1 * oper2)
else:
stack.append(oper2 / oper1)
else:
stack.append(int(element))
# Debug
# print("Stack: ", stack, '\n'
# "Oper1: ", oper1, '\n'
# "Oper2: ", oper2, '\n'
# "element: ", element, '\n')
return stack.pop()
# Test routine
TEST = "77*67+67++*37*/"
TEST2 = "(7*7)*((6+7)+(6+7))/(3*7)"
print("Inputting", TEST, "into postfix_calculator():\n", postfix_calculator(TEST))
print("Inputting", TEST2, "into infix_to_postfix():\n", infix_to_postfix(TEST2))
print("Inputting", TEST2, "into postfix_calculator(infix_to_postfix()): \n",
postfix_calculator(infix_to_postfix(TEST2)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment