<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>

class Solution:
    def calculate(self, expression: str) -> int:
        """Recursive descent.
        """
        OPERATORS = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "*": lambda a, b: a * b,
            "/": lambda a, b: a / b,
        }
        def parse(token_stack: list[tuple[str | int, int]]) -> int:
            negate = 1
            if token_stack[-1][0] == "-":
                token_stack.pop()
                negate = -1
            
            # Descend!
            val = negate * parse_operand(token_stack)

            # Keep reading more operands and operators until the token stream is ended.
            # Or this context is over and an end paren ) is found.
            while len(token_stack) > 0 and token_stack[-1][0] != ")":
                op, pos = token_stack.pop()
                assert op in "+-*/", f"Expected operator at pos {pos}"

                # Descend!
                val2 = parse_operand(token_stack)
                try:
                    val = OPERATORS[op](val, val2)
                except KeyError:
                    raise RuntimeError(f"Unknown operator {op} at pos {pos}")

            return val

        def parse_operand(token_stack: list[tuple[str | int, int]]) -> int:
            top, pos = token_stack.pop()
            if isinstance(top, int):
                return top
            if top == '(':
                val = parse(token_stack)
                top, pos = token_stack.pop()
                assert top == ')', f"No end paren at pos {pos}"
                return val
            raise RuntimeError(f"Expected paren ( or integer at pos {pos}")

        token_stack: list[tuple[str | int, int]] = []
        current_int: tuple[list[str], int] = ([], -1)
        # The sharp/octothorpe/pound/number symbol # is the end of input
        for pos, char in enumerate(expression + "#"):
            if char in "0123456789":
                if not current_int[0]:
                    current_int = ([], pos)
                # Join all integer characters
                current_int[0].append(char)
            elif current_int[0]:
                # Read an entire int
                val = int("".join(current_int[0]))
                token_stack.append((val, current_int[1]))
                current_int = ([], -1)
            # Skip chars
            if char == " ":
                continue
            # Each operator is a single token, even -
            if char in "()+*/-":
                # Since there are no consecutive operators, we don't need lookahead
                token_stack.append((char, pos))
        # First tokens are now at the end where they are removed with .pop()
        token_stack.reverse()
        return parse(token_stack)

36576