"""Evaluate arithmetic expressions with a hand-written recursive descent parser.

Supports + - * / with standard precedence and left associativity, parentheses,
unary + and -, integer and decimal literals, and arbitrary whitespace.
"""


def _tokenize(s):
    """Split the input string into a list of (kind, value) tokens.

    Kinds are: 'NUM' (value is the parsed float), 'OP' (value is one of
    '+', '-', '*', '/'), 'LPAREN', 'RPAREN'. Whitespace is skipped.
    Raises ValueError on any character that cannot start a valid token.
    """
    tokens = []
    i = 0
    n = len(s)
    while i < n:
        c = s[i]
        if c.isspace():
            i += 1
            continue
        if c in '+-*/':
            tokens.append(('OP', c))
            i += 1
            continue
        if c == '(':
            tokens.append(('LPAREN', c))
            i += 1
            continue
        if c == ')':
            tokens.append(('RPAREN', c))
            i += 1
            continue
        if c.isdigit() or c == '.':
            start = i
            seen_dot = False
            while i < n and (s[i].isdigit() or s[i] == '.'):
                if s[i] == '.':
                    if seen_dot:
                        # A second dot in the same number literal is malformed.
                        raise ValueError("malformed number literal: %r" % s[start:i + 1])
                    seen_dot = True
                i += 1
            literal = s[start:i]
            # A lone '.' is not a valid number.
            if literal == '.':
                raise ValueError("malformed number literal: %r" % literal)
            try:
                value = float(literal)
            except ValueError:
                raise ValueError("malformed number literal: %r" % literal)
            tokens.append(('NUM', value))
            continue
        raise ValueError("unknown token: %r" % c)
    return tokens


class _Parser:
    """Recursive descent parser over a flat token list.

    Grammar (precedence from lowest to highest):
        expr   := term (('+' | '-') term)*
        term   := factor (('*' | '/') factor)*
        factor := ('+' | '-') factor | primary
        primary := NUM | '(' expr ')'
    """

    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def _peek(self):
        if self.pos < len(self.tokens):
            return self.tokens[self.pos]
        return None

    def _advance(self):
        tok = self.tokens[self.pos]
        self.pos += 1
        return tok

    def parse(self):
        value = self._expr()
        if self.pos != len(self.tokens):
            # Trailing tokens that were not consumed, e.g. two adjacent
            # numbers ("3 4") or a stray ')'.
            raise ValueError("unexpected trailing input")
        return value

    def _expr(self):
        value = self._term()
        while True:
            tok = self._peek()
            if tok is not None and tok[0] == 'OP' and tok[1] in '+-':
                op = self._advance()[1]
                right = self._term()
                if op == '+':
                    value = value + right
                else:
                    value = value - right
            else:
                break
        return value

    def _term(self):
        value = self._factor()
        while True:
            tok = self._peek()
            if tok is not None and tok[0] == 'OP' and tok[1] in '*/':
                op = self._advance()[1]
                right = self._factor()
                if op == '*':
                    value = value * right
                else:
                    if right == 0:
                        raise ValueError("division by zero")
                    value = value / right
            else:
                break
        return value

    def _factor(self):
        tok = self._peek()
        if tok is None:
            raise ValueError("unexpected end of expression")
        if tok[0] == 'OP' and tok[1] in '+-':
            op = self._advance()[1]
            operand = self._factor()
            if op == '-':
                return -operand
            return operand
        return self._primary()

    def _primary(self):
        tok = self._peek()
        if tok is None:
            raise ValueError("unexpected end of expression")
        if tok[0] == 'NUM':
            self._advance()
            return tok[1]
        if tok[0] == 'LPAREN':
            self._advance()
            value = self._expr()
            closing = self._peek()
            if closing is None or closing[0] != 'RPAREN':
                raise ValueError("mismatched parentheses: missing ')'")
            self._advance()
            return value
        # An OP in operator position (e.g. '*' with no left operand) or a
        # stray ')' lands here.
        raise ValueError("unexpected token: %r" % (tok[1],))


def _normalize(value):
    """Return an int when the value is an exact integer, else a float."""
    if isinstance(value, float):
        if value == int(value) and value not in (float('inf'), float('-inf')):
            return int(value)
        return value
    return value


def eval_expr(s):
    """Evaluate the arithmetic expression in ``s`` and return its value.

    Returns an ``int`` when the result is an exact integer value, otherwise a
    ``float``. Raises ``ValueError`` for any malformed expression (empty input,
    a dangling operator, mismatched parentheses, two adjacent numbers, an
    unknown token) and for division by zero.
    """
    if not isinstance(s, str):
        raise ValueError("expected a string expression")
    tokens = _tokenize(s)
    if not tokens:
        raise ValueError("empty expression")
    parser = _Parser(tokens)
    value = parser.parse()
    return _normalize(value)