Last active
June 30, 2019 11:00
-
-
Save JoseALermaIII/feea6ffa79c730b253a48a587cb78b6c to your computer and use it in GitHub Desktop.
Reverse Polish Notation Calculator
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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