import sys | |
# Constants | |
OPERATORS = ['*', '/', '+', '-'] | |
DECIMAL_SYMBOLS = [',', '.'] | |
SIGN_SYMBOLS = ['-', '+'] | |
PARENTHESIS_OPEN = '(' | |
PARENTHESIS_CLOSE = ')' | |
PRECEDENCE = [[PARENTHESIS_OPEN], ['*', '/'], ['+', '-']] | |
# State variables | |
should_exit = False | |
# Utility functions | |
def subtraction(a, b): | |
if b > 0: | |
return subtraction(a, b - 1) - 1 | |
else: | |
return a | |
def addition(a, b): | |
if b > 0: | |
return addition(a, b - 1) + 1 | |
else: | |
return a | |
def multiplication(a, b): | |
if (b > 0): | |
return addition(multiplication(a, b - 1), a) | |
else: | |
return 0 | |
def division(a, b): | |
if (a > b): | |
return 1 + division(subtraction(a, b), b) | |
else: | |
return 1 | |
OPERATOR_FUNCS = {'-': subtraction, '+': addition, '*': multiplication, '/': division} | |
def halt_error(s): | |
print('invalid expression: %s' % s) | |
sys.exit() | |
def is_operator(s): | |
return s in OPERATORS | |
def tokenize(str): | |
tokens = [] | |
c = [] # Temporary storage for operands | |
s = [] # Set of tokens | |
for cr in str: | |
if cr.isnumeric(): | |
c.append(cr) # Keep track of operand | |
elif cr == PARENTHESIS_OPEN or cr == PARENTHESIS_CLOSE or is_operator(cr): | |
s.append(c) # Push operand | |
c = [] # Empty storage | |
s.append(cr) # Push operator | |
elif cr in DECIMAL_SYMBOLS: | |
halt_error('no support for floating point arithmetic') | |
s.append(c) # Push operand | |
return list(map(''.join, [v for v in s if v])) # Remove empty lists, join each inner list | |
# Returns the intersection of a and b | |
def intersect(a, b): | |
return [v for v in a if v in b] | |
# Returns the nth index of v in l | |
def nth_index(l, v, n): | |
i = -1 | |
for j in range(n): | |
i = l.index(v, i + 1) | |
return i | |
def execute(expr): | |
for group in PRECEDENCE: | |
while len(intersect(expr, group)) > 0: | |
symbol = intersect(expr, group)[0] # Fetch the first operator in the intersection of the precedence group and the expression | |
if (symbol == PARENTHESIS_OPEN): | |
s = expr.index(PARENTHESIS_OPEN) # Find open parenthesis | |
try: | |
e = nth_index(expr, PARENTHESIS_CLOSE, expr.count(PARENTHESIS_OPEN)) | |
sub_expr = expr[s+1:e] # Containing expression | |
new_expr = execute(sub_expr) # New expression resulting from recursive call | |
rem_expr_a = expr[e+1:] # Remaining expression after | |
rem_expr_b = expr[:s] # Remaining expression before | |
expr = rem_expr_b + new_expr + rem_expr_a # Reconstruct expression based on new result | |
except ValueError: | |
halt_error('could not find matching parenthesis ")"') | |
elif (is_operator(symbol)): | |
s = expr.index(symbol) # Find operator | |
a = int(expr[s-1]) # First operand | |
b = int(expr[s+1]) # Second operand | |
new_expr = [OPERATOR_FUNCS[symbol](a, b)] # New expression resulting from operator implementation | |
rem_expr_a = expr[s+2:] # Remaining expression after | |
rem_expr_b = expr[:s-1] # Remaining expression before | |
expr = rem_expr_b + new_expr + rem_expr_a # Reconstruct expression based on new result | |
return expr | |
def bc(str): | |
tokens = tokenize(str) | |
return execute(tokens).pop() | |
#Main logic | |
while not should_exit: | |
s = input('') | |
print(bc(s)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment