<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 {
    int F(vector<string>& tokens, int& i, int multiplier, int& result) {
        if (i >= tokens.size())
            return 0;

        int sign = 1;

        for (; i < tokens.size(); i++) {
            string token = tokens[i];
            if (isdigit(token[0])) {
                result += multiplier * atoi(token.c_str());
            } else if (token == "(") {
                F(tokens, ++i, multiplier * sign, result);
            } else if (token == ")") {
                return result;
            } else if (token == "+") {
                sign = 1;
            } else if (token == "-") {
                sign = -1;
            }
        }
        return 0;
    }

public:
    int calculate(string s) {

        // Step 1: Tokenization
        vector<string> tokens;
        string builder;
        for (char c : s) {
            if (isdigit(c)) {
                builder.push_back(c);
            } else {
                if (builder.size() > 0) {
                    tokens.push_back(builder);
                    builder.clear();
                }
                if (c != ' ') {
                    builder.push_back(c);
                    tokens.push_back(builder);
                    builder.clear();
                }
            }
        }
        if (builder.size() > 0) {
            tokens.push_back(builder);
            builder.clear();
        }

        // Step 2: Calculation
        vector<int> multiplier = {1};
        int sign = 1;
        // int brackets = 0;
        int result = 0;
        int i = 0;
        for (auto& token : tokens) {
            if (token == "+") {
                sign = 1;
            } else if (token == "-") {
                sign = -1;
            } else if (token == "("){
                multiplier.push_back(sign * multiplier.back());
                sign = 1;
            } else if (token == ")"){
                multiplier.pop_back();
            } else {
                result += (sign * multiplier.back() * atoi(token.c_str()));
            }
        }

        return result;
    }
};
29993