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

struct Operand 
{
    string s; 
    bool isDigit = false; 
    bool isLeftPar = false;
    bool isRightPar = false;
    bool isMinus = false;
    bool isPlus = false;
    int val = INT_MIN;
    int sign = 1;
    Operand(const string& _s): s(_s)
    {
        if (s.length() >= 2)
        {
            isDigit = true; 
            val = atoi(s.data());
        }
        else if (('0' <= s[0]) && (s[0] <= '9'))
        {
            isDigit = true; 
            val = s[0] - '0';
        }
        if (s[0] == '(')
        {
            isLeftPar = true;
        }
        if (s[0] == ')')
        {
            isRightPar = true;
        }
        if (s[0] == '+')
        {
            isPlus = true;
        }
        if (s[0] == '-')
        {
            isMinus = true;
        }
    }
};
class Solution {

public:
    int process(string s)
    {
        vector<Operand*> sWords; 
        stack<Operand*> sOperands;
        sWords.push_back(new Operand("("));
        for (int idx = 0; idx < s.length(); idx++)
        {
            if (s[idx] == ' ')
            {
                continue;
            }
            sWords.push_back(new Operand(string(1, s[idx])));
        }
        sWords.push_back(new Operand(")"));

        int curSign = 1;
        for (int idx = 0; idx < sWords.size(); idx++)
        {
            auto& operand = sWords[idx];
            Operand* nextOperand = nullptr;
            Operand* prevOperand = nullptr;
            if ((idx + 1) < sWords.size())
            {
                nextOperand = sWords[idx + 1];
            }
            if (idx - 1 >= 0)
            {
                prevOperand = sWords[idx - 1];
            }
            if (operand->isLeftPar)
            {
                operand->sign = curSign;
                sOperands.push(operand);
                curSign = 1;
            }
            else if (operand->isPlus)
            {
                curSign = 1;
                sOperands.push(operand);
                // cout << "PUSHED +" << endl;
            }
            else if (operand->isMinus)
            {
                curSign = -1;
                if ((prevOperand != nullptr) && ((prevOperand->isDigit || prevOperand->isRightPar)))
                {
                    operand->isMinus = false;
                    operand->isPlus = true;
                    // Pushing the sign to the left parenthesis or the digit. 
                    sOperands.push(operand);
                }
            } 
            else if (operand->isDigit)
            {
                if ((prevOperand != nullptr) && (prevOperand->isDigit))
                {
                    sOperands.top()->val = sOperands.top()->val * 10 + curSign * operand->val;    
                }
                else 
                {
                    operand->val =  curSign * operand->val;
                    // cout << "D" << operand->val << endl;
                    sOperands.push(operand);
                }
            }
            else if (operand->isRightPar)
            {
                int parSign = 1;
                while (true)
                {
                    // Number 
                    if (sOperands.top()->isLeftPar)
                    {
                        // cout << "ONE LEFT" << endl;
                        sOperands.pop();
                        break;
                    }
                    Operand* op1 = sOperands.top();
                    sOperands.pop();
                    cout << op1->val << endl;
                    if (sOperands.top()->isLeftPar)
                    {
                        // cout << "ONE LEFT ONE DIGIT" << endl;
                        parSign = sOperands.top()->sign;
                        sOperands.pop();
                        // cout << "PAR REMOVE" << op1->val << endl;
                        sOperands.push(op1);
                        break;
                    }
                    // Potential operator -> should be always +
                    // cout << "HERE" << endl;
                    Operand* oper = sOperands.top();
                    sOperands.pop();
                    if (!oper->isPlus)
                    {
                        // cout << oper->s <<  "PROBLEM" << endl;
                    }
                    if (sOperands.top()->isLeftPar)
                    {
                        parSign = sOperands.top()->sign;
                        sOperands.pop();
                        sOperands.push(op1);
                        break;
                    }
                    // Potential another number 
                    Operand* op2 = sOperands.top();
                    sOperands.pop();
                    // cout << "HERE 3" << endl;
                    if (sOperands.top()->isLeftPar)
                    {
                        parSign = sOperands.top()->sign;
                    }
                    // cout << "V1: " << op1->val << " " << op2->val << endl;
                    int sum = op1->val + op2->val;
                    sOperands.push(new Operand(to_string(sum)));
                    // cout << "SUM PUSHED" << sOperands.top()->val << endl;
                }
                sOperands.top()->val = parSign * sOperands.top()->val;
                // cout << "TOP AFTER REMOVAL " << sOperands.top()->val << endl;;
            }
        }
        int val = sOperands.top()->val;
        return val;
    }

    int calculate(string s) {
       int val = process(s);
       return val;
    }
};
45931