<p>A <strong>boolean expression</strong> is an expression that evaluates to either <code>true</code> or <code>false</code>. It can be in one of the following shapes:</p>

<ul>
	<li><code>&#39;t&#39;</code> that evaluates to <code>true</code>.</li>
	<li><code>&#39;f&#39;</code> that evaluates to <code>false</code>.</li>
	<li><code>&#39;!(subExpr)&#39;</code> that evaluates to <strong>the logical NOT</strong> of the inner expression <code>subExpr</code>.</li>
	<li><code>&#39;&amp;(subExpr<sub>1</sub>, subExpr<sub>2</sub>, ..., subExpr<sub>n</sub>)&#39;</code> that evaluates to <strong>the logical AND</strong> of the inner expressions <code>subExpr<sub>1</sub>, subExpr<sub>2</sub>, ..., subExpr<sub>n</sub></code> where <code>n &gt;= 1</code>.</li>
	<li><code>&#39;|(subExpr<sub>1</sub>, subExpr<sub>2</sub>, ..., subExpr<sub>n</sub>)&#39;</code> that evaluates to <strong>the logical OR</strong> of the inner expressions <code>subExpr<sub>1</sub>, subExpr<sub>2</sub>, ..., subExpr<sub>n</sub></code> where <code>n &gt;= 1</code>.</li>
</ul>

<p>Given a string <code>expression</code> that represents a <strong>boolean expression</strong>, return <em>the evaluation of that expression</em>.</p>

<p>It is <strong>guaranteed</strong> that the given expression is valid and follows the given rules.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;&amp;(|(f))&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> 
First, evaluate |(f) --&gt; f. The expression is now &quot;&amp;(f)&quot;.
Then, evaluate &amp;(f) --&gt; f. The expression is now &quot;f&quot;.
Finally, return false.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;|(f,f,f,t)&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> The evaluation of (false OR false OR false OR true) is true.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;!(&amp;(f,t))&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> 
First, evaluate &amp;(f,t) --&gt; (false AND true) --&gt; false --&gt; f. The expression is now &quot;!(f)&quot;.
Then, evaluate !(f) --&gt; NOT false --&gt; true. We return true.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= expression.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li>expression[i] is one following characters: <code>&#39;(&#39;</code>, <code>&#39;)&#39;</code>, <code>&#39;&amp;&#39;</code>, <code>&#39;|&#39;</code>, <code>&#39;!&#39;</code>, <code>&#39;t&#39;</code>, <code>&#39;f&#39;</code>, and <code>&#39;,&#39;</code>.</li>
</ul>

class Solution {
public:
    vector<string> parse(string exp){
        // parse the string list of expression into sub expressions
        vector<string> exps;
        int n = exp.size();
        int  cur =0;

        // number of current left brackets
        int left = 0;

        while(cur<n){
            if(exp[cur] =='t'){
                exps.push_back("t");
                cur+=2;
            }
            else if(exp[cur]=='f'){
                exps.push_back("f");
                cur+=2;
            }
            else if(exp[cur]=='!'){
                // find the next )

                left = 0;
                for(int i=cur+1;i<n;++i){
                    if(exp[i]=='(')++left;
                    if(exp[i]==')'){
                        --left;
                        if(left ==0 ){
                            exps.push_back(exp.substr(cur, (i-cur+1)) );
                            cur = i+2;
                            break;
                        }
                    }
                }

            }
            else if( exp[cur]=='&'){
                // find the next )

                left = 0;
                for(int i=cur+1;i<n;++i){
                    if(exp[i]=='(')++left;
                    if(exp[i]==')'){
                        --left;
                        if(left ==0 ){
                            exps.push_back(exp.substr(cur, (i-cur+1)) );
                            cur = i+2;
                            break;
                        }
                    }
                }
            }
            else{
                // find the next )

                left = 0;
                for(int i=cur+1;i<n;++i){
                    if(exp[i]=='(')++left;
                    if(exp[i]==')'){
                        --left;
                        if(left ==0 ){
                            exps.push_back(exp.substr(cur, (i-cur+1)) );
                            cur = i+2;
                            break;
                        }
                    }
                }
            }
        }

        return exps;
    }
    bool valAnd(string exp){
        // seperate into list of expressions 
        // return false from the first false
        vector<string> exps = parse(exp);

        for(int i=0;i<exps.size();++i){
            if(!parseBoolExpr(exps[i]))return false;
        }
        
        return true;
    }
    bool valOr(string exp){
        // seperate into list of expressions
        // return true from the first true
        vector<string> exps = parse(exp);

        for(int i=0;i<exps.size();++i){
            if(parseBoolExpr(exps[i]))return true;
        }

        return false;
    }

    bool valNot(string exp){
        // return the NOT of the expression inside
        return !parseBoolExpr(exp);
    }

    bool parseBoolExpr(string exp) {
        // recurstion
        // split into sub problems

        int n = exp.size();
        bool eval =false;

        if(n==1)return exp[0]=='t';

        if(exp[0]=='&'){
            // if the operation is AND
            eval = valAnd(exp.substr(2,n-3));
        }
        else if(exp[0]=='|'){
            // if the operation is OR
            eval = valOr(exp.substr(2,n-3));
        }
        else{
            // if the operation is NOT
            eval = valNot(exp.substr(2, n-3));
        }

        return eval;
    }
};
13818