<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 dataclasses import dataclass

PRECEDENCE = {
    "+": 0,
    "-": 0,
    "*": 1,
    "/": 1,
}

@dataclass
class Expr:
    op: Literal["+", "-", "*", "/"]
    left: Union["Expr", int]
    right: Union["Expr", int]


class Solution:
    def calculate(self, s: str) -> int:
        return self.eval_expr(self.calculate_at(s, 0)[0])

    def calculate_at(self, s: str, i: int) -> tuple[Expr, int]:
        output_stack = []
        operator_stack = []
        unary_op = None

        expr = None

        while i < len(s):
            x, i = self.token(s, i)

            if isinstance(x, int):
                if expr is None:
                    expr = self.apply_unary_op(x, unary_op)
                else:
                    output_stack.append(x)
            elif x == '(':
                x, i = self.calculate_at(s, i)
                # print("SUBEXPR IS ", x)
                if expr is None:
                    expr = self.apply_unary_op(x, unary_op)
                else:
                    output_stack.append(x)
            elif x == ')':
                break
            elif x == ' ':
                continue
            else:
                # print(x)
                p = PRECEDENCE[x]
                if expr is None:
                    unary_op = x
                    continue

                if operator_stack and p <= PRECEDENCE[operator_stack[-1]]:
                    expr = self.build_expr(expr, output_stack, operator_stack)

                operator_stack.append(x)

        if operator_stack:
            expr = self.build_expr(expr, output_stack, operator_stack)

        # print(expr)

        return expr, i
 
    def token(self, s: str, i: int) -> (str | int, int):
        if s[i].isdigit():
            x = 0

            while i < len(s) and s[i].isdigit():
                x = x * 10 + int(s[i])
                i += 1        
        else:
            x = s[i]
            i += 1

        return x, i

    def build_expr(
        self,
        left: Expr | int,
        output_stack: list[int | Expr],
        operator_stack: list[str]
    ):
        cur_expr = output_stack.pop()
        while len(operator_stack) > 1:
            cur_expr = Expr(
                op=operator_stack.pop(),
                right=cur_expr,
                left=output_stack.pop(),
            )

        return Expr(
            op=operator_stack.pop(),
            right=cur_expr,
            left=left,
        )

    def combine_expr(self, a: Expr | None | int, b: Expr, op: str):
        if a is None:
            return b

        return Expr(
            op,
            a,
            b,
        )

    def apply_unary_op(self, expr: Expr, op: str | None) -> Expr:
        if op:
            return Expr(op, None, expr)
        return expr
    
    def eval_expr(self, expr: Expr | int | None) -> int:
        if expr is None:
            return 0
        if isinstance(expr, int):
            return expr

        if expr.left is None:
            a = expr.right if isinstance(expr.right, int) else self.eval_expr(expr.right)
            return a if expr.op == "+" else -a

        a = expr.left if isinstance(expr.left, int) else self.eval_expr(expr.left)
        b = expr.right if isinstance(expr.right, int) else self.eval_expr(expr.right)

        if expr.op == "+":
            return a + b
        elif expr.op == "-":
            return a - b
        elif expr.op == "*":
            return a * b
        else:
            return a / b
28403