<p>You are given a <strong>valid</strong> boolean expression as a string <code>expression</code> consisting of the characters <code>&#39;1&#39;</code>,<code>&#39;0&#39;</code>,<code>&#39;&amp;&#39;</code> (bitwise <strong>AND</strong> operator),<code>&#39;|&#39;</code> (bitwise <strong>OR</strong> operator),<code>&#39;(&#39;</code>, and <code>&#39;)&#39;</code>.</p>

<ul>
	<li>For example, <code>&quot;()1|1&quot;</code> and <code>&quot;(1)&amp;()&quot;</code> are <strong>not valid</strong> while <code>&quot;1&quot;</code>, <code>&quot;(((1))|(0))&quot;</code>, and <code>&quot;1|(0&amp;(1))&quot;</code> are <strong>valid</strong> expressions.</li>
</ul>

<p>Return<em> the <strong>minimum cost</strong> to change the final value of the expression</em>.</p>

<ul>
	<li>For example, if <code>expression = &quot;1|1|(0&amp;0)&amp;1&quot;</code>, its <strong>value</strong> is <code>1|1|(0&amp;0)&amp;1 = 1|1|0&amp;1 = 1|0&amp;1 = 1&amp;1 = 1</code>. We want to apply operations so that the<strong> new</strong> expression evaluates to <code>0</code>.</li>
</ul>

<p>The <strong>cost</strong> of changing the final value of an expression is the <strong>number of operations</strong> performed on the expression. The types of <strong>operations</strong> are described as follows:</p>

<ul>
	<li>Turn a <code>&#39;1&#39;</code> into a <code>&#39;0&#39;</code>.</li>
	<li>Turn a <code>&#39;0&#39;</code> into a <code>&#39;1&#39;</code>.</li>
	<li>Turn a <code>&#39;&amp;&#39;</code> into a <code>&#39;|&#39;</code>.</li>
	<li>Turn a <code>&#39;|&#39;</code> into a <code>&#39;&amp;&#39;</code>.</li>
</ul>

<p><strong>Note:</strong> <code>&#39;&amp;&#39;</code> does <strong>not</strong> take precedence over <code>&#39;|&#39;</code> in the <strong>order of calculation</strong>. Evaluate parentheses <strong>first</strong>, then in <strong>left-to-right</strong> order.</p>

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

<pre>
<strong>Input:</strong> expression = &quot;1&amp;(0|1)&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can turn &quot;1&amp;(0<u><strong>|</strong></u>1)&quot; into &quot;1&amp;(0<u><strong>&amp;</strong></u>1)&quot; by changing the &#39;|&#39; to a &#39;&amp;&#39; using 1 operation.
The new expression evaluates to 0. 
</pre>

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

<pre>
<strong>Input:</strong> expression = &quot;(0&amp;0)&amp;(0&amp;0&amp;0)&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can turn &quot;(0<u><strong>&amp;0</strong></u>)<strong><u>&amp;</u></strong>(0&amp;0&amp;0)&quot; into &quot;(0<u><strong>|1</strong></u>)<u><strong>|</strong></u>(0&amp;0&amp;0)&quot; using 3 operations.
The new expression evaluates to 1.
</pre>

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

<pre>
<strong>Input:</strong> expression = &quot;(0|(1|0&amp;1))&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can turn &quot;(0|(<u><strong>1</strong></u>|0&amp;1))&quot; into &quot;(0|(<u><strong>0</strong></u>|0&amp;1))&quot; using 1 operation.
The new expression evaluates to 0.</pre>

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

<ul>
	<li><code>1 &lt;= expression.length &lt;= 10<sup>5</sup></code></li>
	<li><code>expression</code>&nbsp;only contains&nbsp;<code>&#39;1&#39;</code>,<code>&#39;0&#39;</code>,<code>&#39;&amp;&#39;</code>,<code>&#39;|&#39;</code>,<code>&#39;(&#39;</code>, and&nbsp;<code>&#39;)&#39;</code></li>
	<li>All parentheses&nbsp;are properly matched.</li>
	<li>There will be no empty parentheses (i.e:&nbsp;<code>&quot;()&quot;</code>&nbsp;is not a substring of&nbsp;<code>expression</code>).</li>
</ul>

class Solution:
    def minOperationsToFlip(self, expression: str) -> int:
        
        class Node:
            def __init__(self, val):
                self.val = val
                self.left = None
                self.right = None
                
        def evaluate(node):
            if node.val == 1 or node.val == 0:
                return node.val
            elif node.val == '|':
                return 1 if evaluate(node.left) or evaluate(node.right) else 0
            else:
                return 1 if evaluate(node.left) and evaluate(node.right) else 0
                
        @cache
        def cost(node, target):
            # If it's a leaf node, cost to make target is 1 if not equal to target, else 0 
            if node.val == 1 or node.val == 0:
                return 0 if node.val == target else 1
            
            elif node.val == '|':
                
                # to make a | b == 1, make either a or b == 1
                if target == 1:
                    return min(cost(node.left, target), cost(node.right, target))
                
                # to make a | b == 0, make a and b == 0, or make | == & and a OR b == 0
                else:
                    return min(cost(node.left, 0) + cost(node.right, 0), 1 + min(cost(node.left, 0), cost(node.right, 0)))
                
            elif node.val == '&':
                # to make a & b == 1, make both a and b equal 1, or make & == | and either a or b == 1
                if target == 1:
                    return min(cost(node.left, 1) + cost(node.right, 1), 1 + min(cost(node.left, 1), cost(node.right, 1)))
                
                # to make a & b == 0, make either a or b 0
                else:
                    return min(cost(node.left, 0), cost(node.right, 0))
            
        q = deque([])
        
        apply = {'|': lambda a,b: 1 if a or b else 0, '&': lambda a,b: 1 if a and b else 0}
        
        for char in expression[::-1]:
            if char == '(':
                # deal with doubled up parentheses e.g. ((1 & 0))
                if len(q) > 1 and q[-2].val == ')':
                    node = q.pop()
                    q.pop() # remove parentheses
                    q.append(node)
                    continue
                    
                # Handle everything inside parentheses
                while q:
                    right = q.pop()
                    op = q.pop()
                    left = q.pop()
                    if q[-1].val == ')':
                        q.pop()
                        op.left = left
                        op.right = right
                        q.append(op)
                        break
                    else:
                        op.left = left
                        op.right = right
                        q.append(op)
            else:
                if char == '1' or char == '0':
                    char = int(char)
                q.append(Node(char))
        
        # All parentheses have been evaluated, now expressions can be processed in order
        while q and len(q) > 1:
            right = q.pop()
            op = q.pop()
            left = q.pop()
            op.left = left
            op.right = right
            q.append(op)
            
        root = q.pop()
        res = evaluate(root)
        
        
        return cost(root, 0 if res else 1)

57500