<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 {
private:
    int getEnd(string expression, int start) {
        if(expression[start] != '(') return -1;
        int count = 0;
        int i = start;
        while(i < expression.length()) {
            if(expression[i] == '(') count++;
            else if(expression[i] == ')') count--;
            if(count == 0) break;
            i++;
        }
        return i;
    }
    bool parseAnd(string expression, int start, int end) {
        if(start >= expression.length()) return false;
        bool res = true;
        int i = start + 1;
        while(i < end) {
            char c = expression[i];
            if(c == ',') {
                i++;
                continue;
            }
            else if(c == 't') {
                res = res && true;
                i++;
            }
            else if(c == 'f') {
                res = false;
                i++;
            }
            else if(c == '&') {
                int j = getEnd(expression, i + 1);
                res = res && parseAnd(expression, i + 1, j);
                i = j + 1;
            } 
            else if(c == '|') {
                int j = getEnd(expression, i + 1);
                res = res && parseOr(expression, i + 1, j);
                i = j + 1;
            }
            else if(c == '!') {
                int j = getEnd(expression, i + 1);
                res = res && parseNot(expression, i + 1, j);
                i = j + 1;
            }
        }
        cout << start << ":" << end << ":" << res << endl;
        return res;
    }
    bool parseOr(string expression, int start, int end) {
        if(start >= expression.length()) return false;
        bool res = false;
        int i = start + 1;
        while(i < end) {
            char c = expression[i];
            if(c == ',') {
                i++;
                continue;
            }
            else if(c == 't') {
                res = true;
                i++;
            }
            else if(c == 'f') {
                res = res || false;
                i++;
            }
            else if(c == '&') {
                int j = getEnd(expression, i + 1);
                res = res || parseAnd(expression, i + 1, j);
                i = j + 1;
            } 
            else if(c == '|') {
                int j = getEnd(expression, i + 1);
                res = res || parseOr(expression, i + 1, j);
                i = j + 1;
            }
            else if(c == '!') {
                int j = getEnd(expression, i + 1);
                res = res || parseNot(expression, i + 1, j);
                i = j + 1;
            }
        }
        cout << start << ":" << end << ":" << res << endl;
        return res;
    }
    bool parseNot(string expression, int start, int end) {
        bool res = !parseBoolExpr(expression.substr(start + 1, end - start - 1));
        cout << start << ":" << end << ":" << res << endl;
        cout << expression.substr(start + 1, end - start - 1) << endl;
        return res;
    }
public:
    bool parseBoolExpr(string expression) {
        char start = expression[0];
        int end = expression.length() - 1;
        if(start == 't') return true;
        if(start == 'f') return false;
        if(start == '&') return parseAnd(expression, 1, end);
        if(start == '|') return parseOr(expression, 1, end);
        if(start == '!') return parseNot(expression, 1, end);
        return false;
    }
};
14181