<p>Given a string <code>s</code> representing a valid expression, implement a basic calculator to evaluate it, and return <em>the result of the evaluation</em>.</p>

<p><strong>Note:</strong> You are <strong>not</strong> allowed to use any built-in function which evaluates strings as mathematical expressions, such as <code>eval()</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;1 + 1&quot;
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot; 2-1 + 2 &quot;
<strong>Output:</strong> 3
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;(1+(4+5+2)-3)+(6+8)&quot;
<strong>Output:</strong> 23
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 3 * 10<sup>5</sup></code></li>
	<li><code>s</code> consists of digits, <code>&#39;+&#39;</code>, <code>&#39;-&#39;</code>, <code>&#39;(&#39;</code>, <code>&#39;)&#39;</code>, and <code>&#39; &#39;</code>.</li>
	<li><code>s</code> represents a valid expression.</li>
	<li><code>&#39;+&#39;</code> is <strong>not</strong> used as a unary operation (i.e., <code>&quot;+1&quot;</code> and <code>&quot;+(2 + 3)&quot;</code> is invalid).</li>
	<li><code>&#39;-&#39;</code> could be used as a unary operation (i.e., <code>&quot;-1&quot;</code> and <code>&quot;-(2 + 3)&quot;</code> is valid).</li>
	<li>There will be no two consecutive operators in the input.</li>
	<li>Every number and running calculation will fit in a signed 32-bit integer.</li>
</ul>

from abc import ABC, abstractmethod
from dataclasses import dataclass
from typing import Callable, Iterable, Literal, TypeAlias, assert_never

TokenTypes: TypeAlias = Literal[
    "Number", "Plus", "Minus", "LeftParenthesis", "RightParenthesis", "EOF"
]
LiteralValue: TypeAlias = int


@dataclass
class Token:
    token_type: TokenTypes
    lexeme: str
    position: int
    literal: LiteralValue | None


class Lexer:
    def __init__(self, source: str):
        self.source = source
        self.start = 0
        self.current = 0
        return super().__init__()

    def exhausted(self):
        return self.current >= len(self.source)

    def _consume(self):
        return self.source[self._advance()]

    def _peek(self):
        return None if self.exhausted() else self.source[self.current]

    def _advance(self):
        self.current = (current := self.current) + 1
        return current

    def _make(
        self, token_type: TokenTypes, parse: Callable[[str], LiteralValue] | None = None
    ):
        lexeme = self._lexeme()
        literal = None if parse is None else parse(lexeme)
        return Token(token_type, lexeme, self.start, literal)

    def _lexeme(self):
        return self.source[self.start : self.current]

    def __iter__(self):
        return self

    def __next__(self):
        while not self.exhausted():
            if (token := self._get()) is not None:
                return token
        raise StopIteration

    def _get(self):
        self.start = self.current
        match (consumed := self._consume()):
            case " ":
                return None
            case "(":
                return self._make("LeftParenthesis")
            case ")":
                return self._make("RightParenthesis")
            case "+":
                return self._make("Plus")
            case "-":
                return self._make("Minus")
            case d if d.isdigit():
                while (peek := self._peek()) is not None and peek.isdigit():
                    self._advance()
                return self._make("Number", int)
            case other:
                raise ValueError(f"Invalid token {other!r}!")
        assert_never(consumed)


class Expression(ABC):
    @abstractmethod
    def evaluate(self) -> int: ...

    @abstractmethod
    def __str__(self) -> str: ...


class NumberLiteral(Expression):
    def __init__(self, value: int):
        self.value = value
        return super().__init__()

    def evaluate(self) -> int:
        return self.value

    def __str__(self) -> str:
        return str(self.value)


class UnaryExpression(Expression):
    def __init__(self, expr: Expression, operator: Token):
        self.expr = expr
        self.operator = operator
        return super().__init__()

    def evaluate(self) -> int:
        value = self.expr.evaluate()
        match (token_type := self.operator.token_type):
            case "Minus":
                return -value
            case other:
                raise Exception(f"Invalid unary expression token {other!r}!")
        assert_never(token_type)

    def __str__(self) -> str:
        return f"({self.operator.token_type} {self.expr})"


class BinaryExpression(Expression):
    def __init__(self, left: Expression, operator: Token, right: Expression):
        self.left = left
        self.operator = operator
        self.right = right
        return super().__init__()

    def evaluate(self) -> int:
        left = self.left.evaluate()
        right = self.right.evaluate()
        match (token_type := self.operator.token_type):
            case "Plus":
                return left + right
            case "Minus":
                return left - right
            case other:
                raise Exception(f"Invalid binary expression token {other!r}!")
        assert_never(token_type)

    def __str__(self) -> str:
        return f"({self.operator.token_type} {self.left} {self.right})"


class ParseException(Exception):
    def __init__(self, token: Token | None, message: str, *args: object):
        self.token = token
        super().__init__(message, *args)


class Parser:
    def __init__(self, tokens: Iterable[Token]):
        self.tokens = iter(tokens)
        self._exhausted = False
        self._peeked = None
        return super().__init__()

    def _match_any(self, *expected: TokenTypes):
        for exp in expected:
            if (matched := self._match(exp)) is not None:
                return matched
        return None

    def _match(self, expected: TokenTypes):
        if self._exhausted:
            return None
        if (token := self._peek()) is not None and token.token_type == expected:
            return self._advance()
        return None

    def _peek(self):
        if (peeked := self._peeked) is not None:
            return peeked
        peeked = self._advance()
        self._peeked = peeked
        return peeked

    def _advance(self):
        if (peeked := self._peeked) is not None:
            self._peeked = None
            return peeked
        try:
            return next(self.tokens)
        except StopIteration:
            return None

    def _left_assoc(self, read: Callable[[], Expression], *infix: TokenTypes):
        expr = read()
        while (matched := self._match_any(*infix)) is not None:
            right = read()
            expr = BinaryExpression(expr, matched, right)
        return expr

    def consume(self, expected: TokenTypes):
        if (matched := self._match(expected)) is None:
            peek = self._peek()
            gotten = "nothing" if peek is None else peek.token_type
            raise ParseException(peek, f"Expected {expected}, but got {gotten}!")
        return matched

    def expression(self) -> Expression:
        return self.term()

    def term(self):
        return self._left_assoc(self.unary, "Plus", "Minus")

    def unary(self) -> Expression:
        if (matched := self._match_any("Minus")) is not None:
            expr = self.unary()
            return UnaryExpression(expr, matched)
        return self.primary()

    def primary(self):
        if self._match("LeftParenthesis") is not None:
            expr = self.expression()
            self.consume("RightParenthesis")
            return expr
        number = self.consume("Number")
        if (literal := number.literal) is None:
            raise Exception("Found number token without literal!")
        return NumberLiteral(literal)


class Solution:
    def calculate(self, s: str) -> int:
        lexer = Lexer(s)
        parser = Parser(lexer)
        try:
            expr = parser.expression()
        except ParseException as e:
            if (token := e.token) is not None:
                start = token.position
                end = start + len(token.lexeme)
                highlight = f"{s[:start]} > {s[start:end]} < {s[end:]}"
                e.add_note(f"Error at: {highlight}")
            raise e
        return expr.evaluate()


def main():
    solution = Solution()
    assert solution.calculate("1 + 1") == 2
    assert solution.calculate(" 2-1 + 2 ") == 3
    assert solution.calculate("(1+(4+5+2)-3)+(6+8)") == 23
    assert solution.calculate("-(4+5)") == -9
    try:
        solution.calculate("(1+((4+5+2)-3)+(6+8)")
        raise Exception("Expected a parse exception!")
    except ParseException as e:
        assert e.args[0] == "Expected RightParenthesis, but got nothing!"


if __name__ == "__main__":
    main()

44121