<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 opposign(int num){
        return -num;
    }
    string calculated(string &s){
        int sign=1,i=1;
        if(s[0]!='-'){
            sign=0,i=0;
        }
        int ans=0;
        while(i<s.size() and s[i]>='0' and s[i]<='9'){
             ans=ans*10+(s[i]-'0');
             i++;
        }
        if(sign) ans=opposign(ans);
       // cout<<"ans "<<ans<<endl;
        while(i<s.size()){
             if(s[i]=='-'){
                sign=1;
             }
             else{
                sign=0;
             }
             int val=0;
             i++;
             while(i<s.size() and s[i]>='0' and s[i]<='9'){
                val=val*10+(s[i]-'0');
                i++;
             }
            // cout<<"val "<<val<<endl;
             if(sign) ans-=val;
             else ans+=val;
        }
        return to_string(ans);
    }
    void push(stack<char>&st,string &s,int start){
        while(start<s.size()) st.push(s[start]),start++;
    }
    int cal(string &temp){
        stack<char>st;
        for(int i=0;i<temp.size();i++){
            if(temp[i]==')'){
                string newtemp="";
                while(st.top()!='('){
                    newtemp+=st.top();
                    st.pop();
                }
                reverse(newtemp.begin(),newtemp.end());
                st.pop();
                string newres=calculated(newtemp);
                if(st.size()==0){
                     push(st,newres,0);
                }
                else{
                    if(st.top()=='-'){
                        if(newres.size()>0){
                            if(newres[0]=='-'){
                                st.pop();
                                st.push('+');
                                push(st,newres,1);
                            }
                            else{
                                push(st,newres,0);
                            }
                        }
                    }
                    else{
                         push(st,newres,0);
                    }
                }
            }
            else{
                st.push(temp[i]);
            }
        }
        string ans="";
        while(st.size()>0){
            ans+=st.top(),st.pop();
        }
        reverse(ans.begin(),ans.end());
        //cout<<ans<<endl;
       // ans=calculated(ans);
        // for(auto it:ans){
        //     cout<<it<<" ";
        // }
        return stoi(calculated(ans));
    }
    int calculate(string s) {
        string temp="";
        string temp1="";
        for(int i=0;i<s.size();i++){
            if(s[i]==' ') continue;
            temp+=s[i];
        }
        //cout<<calculated(temp)<<endl;
        return cal(temp);
    }
};
14056