Skip to content

Instantly share code, notes, and snippets.

@ofx ofx/bc.py
Created Jul 18, 2018

Embed
What would you like to do?
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
You can’t perform that action at this time.