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

    enum class NextOperation: uint8_t
    {
        ADD,
        SUBSTRACT
    };

    int computeCurrentLine(string s)
    {
//        std::cout << "Processing " << std::quoted(s) << std::endl;
        if ((s.front() == '(') and (s.back() == ')'))
            s = s.substr(1, s.length() - 2);

        vector<string> operands;
        size_t i = 0;
        while (i < s.length())
        {
//          std::cout << "Processing at " << i << std::endl;
            size_t nextToken = s.find_first_of("+- ", i);
            if (nextToken != std::string::npos)
            {
//                std::cout << "Token found at " << nextToken << std::endl;
                if (nextToken > i)
                {
                    operands.push_back(s.substr(i, nextToken - i));
//                    std::cout << "Storing 1 " << std::quoted(s.substr(i, nextToken - i)) << std::endl;                
                }
                operands.push_back(s.substr(nextToken, 1));
//                std::cout << "Storing 2 " << std::quoted(s.substr(nextToken, 1)) << std::endl;

                i = nextToken + 1;
            }
            else
            {
                operands.push_back(s.substr(i, s.length() - i));
//                std::cout << "Storing 3 " << std::quoted(s.substr(i, s.length() - i)) << std::endl;
                break;
            }
        }

        // Now, traverse the operands line by line
        int result = 0;
        NextOperation nextOp = NextOperation::ADD;
        for (auto const &operand : operands)
        {
//            std::cout << "Operand " << std::quoted(operand) << std::endl;
            if (operand == "-")
            {
                if (nextOp == NextOperation::ADD)
                    nextOp = NextOperation::SUBSTRACT;
                else
                    nextOp = NextOperation::ADD;
            }                
            else if (operand == "+")
                nextOp = NextOperation::ADD;
            else if (operand == " ")
                continue;
            else
            {
                switch (nextOp)
                {
                    case NextOperation::SUBSTRACT:
                        result -= std::stoi(operand);
                        break;
                    case NextOperation::ADD:
                        result += std::stoi(operand);
                        break;
                    default:
                        break;                    
                }
                nextOp = NextOperation::ADD;
            }
        }
//        std::cout << "Compute returned " << result << std::endl;
        return result;
    }

    int calculate(string s) {
        // Parse string until a '(' is found.
        // In that case, start a stack until either a ')' is found
        // in which case the stack is parsed, or, if a new '(' is found,
        // a subsequent stack is started and so on
        int result = 0;
        vector<string> parser;
        for (auto const &c: s)
        {
            if (c == '(')
            {
                parser.push_back(std::string(1, c));
            }
            else if (c == ')')
            {
                parser.back().append(1, c);
                // Parse the current line
                result = computeCurrentLine(parser.back());
                // Append the result to the previous line
                parser.pop_back();
                if (parser.empty())
                    parser.push_back(std::to_string(result));
                else
                    parser.back().append(std::to_string(result));
            }
            else
            {
                if (parser.empty())
                    parser.push_back(std::string(1, c));
                else
                    parser.back().append(1, c);
            }
        }

        if (parser.size() != 1)
            return 0;

        return computeCurrentLine(parser.back());
    }
};
40306