#!/usr/bin/env python3
"""Arithmetic expression evaluator without eval."""

from typing import List, Optional, Tuple, Union


def eval_expr(s: str) -> Union[int, float]:
    tokens = _tokenize(s)
    if not tokens:
        raise ValueError("empty expression")
    value, pos = _parse_expr(tokens, 0)
    if pos != len(tokens):
        raise ValueError("malformed expression")
    return _normalize(value)


def _normalize(x: float) -> Union[int, float]:
    if isinstance(x, bool):
        return x
    if isinstance(x, (int, float)) and float(x).is_integer():
        return int(x)
    return float(x)


def _tokenize(s: str) -> List[str]:
    tokens: List[str] = []
    i = 0
    n = len(s)
    while i < n:
        c = s[i]
        if c.isspace():
            i += 1
            continue
        if c in "+-*/()":
            tokens.append(c)
            i += 1
            continue
        if c.isdigit() or c == ".":
            j = i
            has_dot = False
            while j < n and (s[j].isdigit() or s[j] == "."):
                if s[j] == ".":
                    if has_dot:
                        raise ValueError("invalid number")
                    has_dot = True
                j += 1
            num = s[i:j]
            if num == "." or num.count(".") > 1:
                raise ValueError("invalid number")
            if not any(ch.isdigit() for ch in num):
                raise ValueError("invalid number")
            tokens.append(num)
            i = j
            continue
        raise ValueError(f"unknown token near {c!r}")
    return tokens


def _parse_expr(tokens: List[str], pos: int) -> Tuple[float, int]:
    left, pos = _parse_term(tokens, pos)
    while pos < len(tokens) and tokens[pos] in ("+", "-"):
        op = tokens[pos]
        pos += 1
        right, pos = _parse_term(tokens, pos)
        if op == "+":
            left = left + right
        else:
            left = left - right
    return left, pos


def _parse_term(tokens: List[str], pos: int) -> Tuple[float, int]:
    left, pos = _parse_unary(tokens, pos)
    while pos < len(tokens) and tokens[pos] in ("*", "/"):
        op = tokens[pos]
        pos += 1
        right, pos = _parse_unary(tokens, pos)
        if op == "*":
            left = left * right
        else:
            if right == 0:
                raise ValueError("division by zero")
            left = left / right
    return left, pos


def _parse_unary(tokens: List[str], pos: int) -> Tuple[float, int]:
    if pos >= len(tokens):
        raise ValueError("unexpected end of expression")
    if tokens[pos] == "+":
        return _parse_unary(tokens, pos + 1)
    if tokens[pos] == "-":
        val, pos = _parse_unary(tokens, pos + 1)
        return -val, pos
    return _parse_primary(tokens, pos)


def _parse_primary(tokens: List[str], pos: int) -> Tuple[float, int]:
    if pos >= len(tokens):
        raise ValueError("unexpected end of expression")
    t = tokens[pos]
    if t == "(":
        val, pos = _parse_expr(tokens, pos + 1)
        if pos >= len(tokens) or tokens[pos] != ")":
            raise ValueError("mismatched parentheses")
        return val, pos + 1
    if t in ("+", "-", "*", "/", ")"):
        raise ValueError("malformed expression")
    # number
    try:
        if "." in t:
            val = float(t)
        else:
            val = float(int(t))
    except ValueError:
        raise ValueError("invalid number") from None
    return val, pos + 1