<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:
    int get(char c){
        // if(c=='|') return 0;
        
        if(c=='|') return 1;
        if(c=='&') return 2;
        if(c=='!') return 3;
        return 0;
    }
    bool f(string str,int l){
        int sign =get(str[0]);
        cout<<"sign is "<<sign<<endl;
    
        bool ans=str[2]=='f'?false:true;
        cout<<str<<" "<<l<<endl;
        if(sign==3) return !ans;

        if(sign==1){
            for(int i=3;i<l;i++){
                bool q=str[i]=='f'?false:true;
                ans=ans|q;
                cout<<"ans is "<<ans<<endl;
            }
        }

        else if(sign==2){
            for(int i=3;i<l;i++){
                bool q=str[i]=='f'?false:true;
                ans=ans&q;
                cout<<"ans is "<<ans<<endl;
            }

        }
        return ans;
    }



    bool parseBoolExpr(string exp) {
        stack<char> s;
        char ans;
        for(int i=0;i<exp.length();i++){
            s.push(exp[i]);
        }
        // &(|(f))
        string str="";
        int last=-1;
        while(!s.empty()){
            char curr=s.top();
            // cout<<curr<<" ";
            ans=curr;
            s.pop();
            if(curr==',') continue;
            str=curr+str;
            if(curr==')') last=str.length();
            if(curr=='|' ||curr=='&' || curr=='!'){
                cout<<str<<endl;
                int len=str.length()-last;
                bool z=f(str,len);
                cout<<"z is "<<z<<endl;
                if(z==false)  s.push('f');
                else s.push('t');
                string s2="";
                if(str[len]==')') len++;
                for(int i=len;i<str.length();i++){
                    s2+=str[i];
                }
                str="";
                for(int j=0;j<s2.length();j++){
                    s.push(s2[j]);
                }
                // str=str.substr();
            }
        }
    if(ans=='f') return false;
    return true;
    }
};
19256