Skip to content

Instantly share code, notes, and snippets.

@justinnhli
Created July 19, 2021 23:42
Show Gist options
  • Save justinnhli/0622cf88e220b37127124eb4d01b193b to your computer and use it in GitHub Desktop.
Save justinnhli/0622cf88e220b37127124eb4d01b193b to your computer and use it in GitHub Desktop.
#!/usr/bin/env python3
"""A recursive-descent arithmetic calculator."""
import re
from collections import namedtuple
from fractions import Fraction
Parse = namedtuple('Parse', 'value, index')
FAILURE = Parse(None, -1)
def next_non_blank(string, index):
# type: (str, int) -> int
"""Find the next non-blank character.
Parameters:
string (str): The string to be parsed.
index (int): The index to start looking.
Returns:
int: The index of the next non-blank character, or the length of the string.
"""
if index >= len(string):
return index
while index < len(string) and string[index] in '\t ':
index += 1
return index
def parse_number(string, index):
# type: (str, int) -> Parse
"""Parse a number.
Parameters:
string (str): The string to be parsed.
index (int): The index to start parsing.
Returns:
Parse: The value of the number and the index parsed so far.
"""
match = re.match(r'-?[0-9]*(\.[0-9]+)?', string[index:])
if match and match.group(0) != '':
return Parse(Fraction(match.group(0)), index + len(match.group(0)))
else:
return FAILURE
def parse_paren(string, index):
# type: (str, int) -> Parse
"""Parse a parenthesized expression.
Parameters:
string (str): The string to be parsed.
index (int): The index to start parsing.
Returns:
Parse: The value of the expression and the index parsed so far.
"""
index = next_non_blank(string, index)
if string[index] != '(':
return FAILURE
index += 1
result, index = parse(string, index, 'add_sub')
if index == -1:
return FAILURE
index = next_non_blank(string, index)
if index == len(string) or string[index] != ')':
return FAILURE
return Parse(result, index + 1)
def parse_operand(string, index):
# type: (str, int) -> Parse
"""Parse an operand (a number or a parenthesized expression).
Parameters:
string (str): The string to be parsed.
index (int): The index to start parsing.
Returns:
Parse: The value of the expression and the index parsed so far.
"""
index = next_non_blank(string, index)
result, result_index = parse(string, index, 'paren')
if result_index != -1:
return Parse(result, result_index)
return parse(string, index, 'number')
def parse_mul_div(string, index):
# type: (str, int) -> Parse
"""Parse a multiplication/division expression.
Parameters:
string (str): The string to be parsed.
index (int): The index to start parsing.
Returns:
Parse: The value of the expression and the index parsed so far.
Raises:
ZeroDivisionError: If there is a divide by zero.
"""
index = next_non_blank(string, index)
result = parse(string, index, 'operand')
if result.index == -1 or result.index > len(string):
return FAILURE
while True:
index = next_non_blank(string, result.index)
if index == len(string):
break
if string[index] in '*/':
operator = string[index]
index += 1
else:
break
operand, index = parse(string, next_non_blank(string, index), 'operand')
if index == -1:
return FAILURE
if operand == 0:
raise ZeroDivisionError()
if operator == '*':
result = Parse(result.value * operand, index)
else:
result = Parse(result.value / operand, index)
return result
def parse_add_sub(string, index):
# type: (str, int) -> Parse
"""Parse an addition/subtraction expression.
Parameters:
string (str): The string to be parsed.
index (int): The index to start parsing.
Returns:
Parse: The value of the expression and the index parsed so far.
"""
index = next_non_blank(string, index)
result = parse(string, index, 'mul_div')
if result.index == -1 or result.index > len(string):
return FAILURE
while True:
index = next_non_blank(string, result.index)
if index == len(string):
break
if string[index] in '+-':
operator = string[index]
index += 1
else:
break
operand, index = parse(string, next_non_blank(string, index), 'mul_div')
if index == -1:
return FAILURE
if operator == '+':
result = Parse(result.value + operand, index)
else:
result = Parse(result.value - operand, index)
return result
def parse(string, index=0, term='add_sub'):
# type: (str, int, str) -> Parse
"""Dispatch an arithmetic expression to be parsed.
Parameters:
string (str): The string to be parsed.
index (int): The index to start parsing. Defaults to 0.
term (str): The term to parse as. Defaults to 'add_sub'
Returns:
Parse: The value of the expression and the index parsed so far.
Raises:
ValueError: If the term is unknown.
"""
if index > len(string):
return FAILURE
elif term == 'number':
return parse_number(string, index)
elif term == 'paren':
return parse_paren(string, index)
elif term == 'operand':
return parse_operand(string, index)
elif term == 'mul_div':
return parse_mul_div(string, index)
elif term == 'add_sub':
return parse_add_sub(string, index)
else:
raise ValueError(f'unexpected term: {term}')
def calculate(string):
# type: (str) -> Fraction
"""Evaluate an arithmetic expression.
Parameters:
string (str): The string to be parsed.
Returns:
Fraction: The value of the expression.
Raises:
SyntaxError: If the expression is not well formed.
"""
result, index = parse(string)
index = next_non_blank(string, index)
if index == -1 or index != len(string):
raise SyntaxError()
return result
def test():
# type: () -> None
"""Test the calculator.
Raises:
AssertionError: If the tests fail.
"""
assert calculate('3.14') == Fraction(314, 100)
assert calculate('1') == 1
assert calculate('1/2') == Fraction(1, 2)
assert calculate('1*2/3') == Fraction(2, 3)
assert calculate('2+2*2') == 6
assert calculate('(2+2)') == 4
assert calculate('1/3 + 1/3 + 1/3') == 1
assert calculate('(2+2)*2') == 8
def main():
# type: () -> None
"""Provide a CLI entry point."""
test()
while True:
try:
result = calculate(input('> '))
if int(result) == result:
print(int(result))
else:
print(float(result))
except ZeroDivisionError:
print('divide by zero')
except SyntaxError:
print('syntax error')
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment