<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 {
public:
    int calculate(string &s) {
        int ans = 0, sign = 1, number = 0; // `number` stores the current number
        stack<int> stk;
        stk.push(sign);
        for (char c : s) {
            if (isdigit(c)) number = number * 10 + (c - '0');
            else if (c == '+' || c == '-') { // (¶)
                ans += sign * number;
                number = 0;
                sign = stk.top() * (c == '+' ? 1 : -1); // note that `sign` can only be 1 or –1 (§)
            }
            else if (c == '(') stk.push(sign);
            else if (c == ')') stk.pop(); // the influence of the sign at the top of the stack has ended
        }
        ans += sign * number;
        return ans;
    }
}; // Calculatrice de base 基本的な計算機（・計算器・けいさんき）［電卓・でんたく：「電子式卓上計算機（でんししきたくじょうけいさんき）また電子式卓上加算機」の略］
// Comparison: in the previous submission, we used the stack to store operands and operators (as well as results): when we encounter a right parenthesis (ie ')'), we start doing the calculation, popping from the stack until we encounter a left parenthesis. Essentially, we only update the answer when we encounter a right parenthesis (and after the loop ends).
// (§) But here, we update the answer for each number (and after the loop ends). Conceptually, we are (開括號) opening the parentheses on-the-fly. To achieve this, we only use the stack to store the signs so that we can check, for each number, what is the sign outside its closest left parenthesis. For instance, consider the input string "–2–(1–(4+5–(–7–2)+2)–3)–(6+8)". Note that the expression E1 = –2–(1–(4+5–(–7–2)+2)–3)–(6+8) is equivalent to the expression E2 = –2–1+4+5+7+2+2+3–6–8. When we encounter the first left parenthesis in E1, we push into the stack a minus sign, so when we encouter 1, we know its sign is negative (which is the same as the sign of 1 in E2). When we encounter the second left parenthesis, we see the sign in front of it is a minus sign, and we check the top of the stack, which is also a minus sign, we know the sign should be positive so we push a plus sign into the stack: thus when we encounter 4, we know it is positive (which is the same as the sign of 4 in E2)
// So, here the algorithm is essentially doing this:
//   –2–1+4+5+7+2+2+3–6–8
// = –3+4+5+7+2+2+3–6–8
// = 1+5+7+2+2+3–6–8
// = 6+7+2+2+3–6–8
// = 13+2+2+3–6–8
// = 15+2+3–6–8
// = 17+3–6–8
// = 20–6–8
// = 14–8
// = 6
// For comparison, in the previous submission, we are essentially doing this: 
//   –2–(1–(4+5–(–7–2)+2)–3)–(6+8)
// = –2–(1–(4+5––9+2)–3)–(6+8)
// = –2–(1–(4+5+9+2)–3)–(6+8)
// = –2–(1–(4+5+11)–3)–(6+8)
// = –2–(1–(4+16)–3)–(6+8)
// = –2–(1–20–3)–(6+8)
// = –2–(1–23)–(6+8)
// = –2––22–(6+8)
// = –2––22–14
// = –2+22–14
// = –2+8
// = 6
// (¶) we deal with the current number. and determine the sign of the next number
9368