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

from enum import Enum


class Solution:
    class NodeType(Enum):
        ROOT = 1
        AND = 2
        OR = 3
        NOT = 4
        ATOMIC = 5

    class Node:
        def __init__(self, type, children=[], value=False, parent=None):
            self.type = type
            self.children = children
            self.value = value
            self.parent = parent

    class State:
        INIT = 1

    def recurse(self, node: Node) -> bool:
        if node.type == self.NodeType.ROOT:
            return self.recurse(node.children[0])
        elif node.type == self.NodeType.AND:
            for c in node.children:
                if self.recurse(c) == False:
                    return False
            return True
        elif node.type == self.NodeType.OR:
            for c in node.children:
                if self.recurse(c) == True:
                    return True
            return False
        elif node.type == self.NodeType.NOT:
            return not self.recurse(node.children[0])
        elif node.type == self.NodeType.ATOMIC:
            return node.value

    def parseBoolExpr(self, expression: str) -> bool:
        rootNode = self.Node(self.NodeType.ROOT, [])
        curNode = rootNode
        for c in expression:
            if c == "t":
                curNode.children.append(
                    self.Node(self.NodeType.ATOMIC, [], True, curNode)
                )
            elif c == "f":
                curNode.children.append(
                    self.Node(self.NodeType.ATOMIC, [], False, curNode)
                )
            elif c == "!":
                new = self.Node(self.NodeType.NOT, [], True, curNode)
                curNode.children.append(new)
                curNode = new
            elif c == "&":
                new = self.Node(self.NodeType.AND, [], True, curNode)
                curNode.children.append(new)
                curNode = new
            elif c == "|":
                new = self.Node(self.NodeType.OR, [], True, curNode)
                curNode.children.append(new)
                curNode = new
            elif c == "(":
                pass
            elif c == ")":
                curNode = curNode.parent
            elif c == ",":
                pass
        return self.recurse(rootNode)

19900