<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, s: str) -> int:
        # We first translate the string to use no spaces and
        #   then recursive descent.
        def read_all(start):
            if s[start] != "-":
                first, rest = read_term(start)
            else:
                neg_first, rest = read_term(start+1)
                first = -neg_first 
            if rest!=len(s) and (operator := s[rest]) in "+-" :
                assert len(s)-rest >= 2
                # Interpret "-" as "+-"
                if operator == "+":
                    second, rest = read_all(rest+1)
                else:
                    second, rest = read_all(rest)
                return first+second, rest
            else:
                return first, rest

        def read_num(start):
            end = start
            while end < len(s) and s[end] in "0123456789":
                end += 1
            if end!=start:
                return int(s[start:end]), end
            return None

        def read_term(start):
            if (ret := read_num(start)) is not None:
                return ret
            if s[start] == "(":
                res, rest = read_all(start+1)
                assert s[rest] == ")"
                return res, rest+1
            if s[start] == "-":
                neg_res, rest = read_term(start+1)
                return -neg_res, rest
            # print(s)
            assert False

        s = "".join( c for c in s if c!=" ")
        ret, rest = read_all(0)
        assert rest==len(s)
        return ret
27145