Simple S-Expression Evaluator

parse.py

# Grammar:
# expr   = number
#        | "(" op expr+ ")"
# op     = "+" | "-" | "*" | "/"
# number = "-"? DIGIT+

import re
from functools import reduce
from typing import Any, List, Optional, Tuple, Union

# Type aliases
ParsedValue = Any
ConsumedInput = int
RuleMatch = Tuple[ParsedValue, ConsumedInput]
RuleReturn = Optional[RuleMatch]

Numeric = Union[int, float]

# Standard functions
# Each of type: List[Numeric] -> Numeric
stdlib = {
    '+': lambda x: reduce(lambda a, b: a + b, x),
    '-': lambda x: reduce(lambda a, b: a - b, x),
    '*': lambda x: reduce(lambda a, b: a * b, x),
    '/': lambda x: reduce(lambda a, b: a / b, x)
}

# Grammar rules
def expr(data:str) -> RuleReturn:
    number_match = number(data)
    if number_match:
        return number_match

    open_match = open_paren(data)
    if not open_match:
        print('Invalid expression: No opening parenthesis')
        return None

    cursor = open_match[1]
    op_match = op(data[cursor:])
    if not op_match:
        print('Invalid expression: No operator found')
        return None

    args = []
    cursor += op_match[1]

    while True:
        # We need at least one argument
        expr_match = expr(data[cursor:])
        if not expr_match:
            print('Invalid expression: Invalid argument "%s"' % data[cursor:])
            return None

        # expr_match[0] is the evaluated expression value
        args.append(expr_match[0])
        cursor += expr_match[1]

        # Break when we reach a closing parenthesis
        close_match = close_paren(data[cursor:])
        if close_match:
            cursor += close_match[1]
            break

    # op_match[0] is the stdlib lambda function
    return op_match[0](args), cursor

def open_paren(data:str) -> RuleReturn:
    match = re.match(r'^\s*\(', data)
    if not match:
        return None

    consumed = len(match.group(0))
    return None, consumed

def close_paren(data:str) -> RuleReturn:
    match = re.match(r'^\s*\)', data)
    if not match:
        return None

    consumed = len(match.group(0))
    return None, consumed

def number(data:str) -> RuleReturn:
    match = re.match(r'^\s*(-?\d+)\b', data)
    if not match:
        return None

    value = int(match.group(1))
    consumed = len(match.group(0))
    return value, consumed

def op(data:str) -> RuleReturn:
    match = re.match(r'^\s*([-+*/])', data)
    if not match:
        return None

    value = stdlib[match.group(1)]
    consumed = len(match.group(0))
    return value, consumed

# Evaluator (wrapper)
def eval(data:str) -> Optional[Numeric]:
    result, _ = expr(data) or (None, None)
    return result