calculator.py

#!/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()