<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 TreeNode:
    def __init__(self, val, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right
    
    def eval(self):
        if self.val in "01":
            return int(self.val)
        
        l, r = self.left.eval(), self.right.eval()
        if self.val == "|":
            return 1 if l + r >= 1 else 0
        else:
            return 1 if l + r == 2 else 0
    

    

class Solution:
    def buildTree(self, s):
        n = len(s)
        def dfs(idx):
            stack = []
            while idx < n:
                c = s[idx]
                if c == "(":
                    res, l = dfs(idx + 1)
                    stack.append(res)
                    idx = l
                elif c == ")":
                    return stack, idx
                else:
                    stack.append(c)
                idx += 1
            return stack
        array = dfs(0)
        ops = []

        def build(arr, start, end):
            if start == end:
                if arr[start] == "1" or arr[start] == "0":
                    return TreeNode(arr[start])
                elif isinstance(arr[start], list):
                    return build(arr[start], 0, len(arr[start]) - 1)
            
            ops = []
            for i in range(end, start - 1, -1):
                if arr[i] == "|" or arr[i] == "&":
                    idx = i
                    break
            left = build(arr, start, idx - 1)
            right = build(arr, idx + 1, end)
            return TreeNode(arr[idx], left, right)
        
        return build(array, 0, len(array) - 1)
                    

    def minOperationsToFlip(self, expression: str) -> int:
        root = self.buildTree(expression)
        res = root.eval()

        @lru_cache(None)
        def dfs(node, target):
            if node.val in "01":
                return 1 if int(node.val) != target else 0
            ans = float('inf')
            if target == 0:
                if node.val == "&":
                    ans = min(ans, min(dfs(node.left, 0), dfs(node.right, 0)))
                elif node.val == "|":
                    ans = min(ans, dfs(node.left, 0) + dfs(node.right, 0))
                    ans = min(ans, 1 + min(dfs(node.left, 0), dfs(node.right, 0)))
            else:
                if node.val == "&":
                    ans = min(ans, dfs(node.left, 1) + dfs(node.right, 1))
                    ans = min(ans, 1 + min(dfs(node.left, 1), dfs(node.right, 1)))
                elif node.val == "|":
                    ans = min(ans, min(dfs(node.left, 1), dfs(node.right, 1)))
            return ans

        return dfs(root, 1 - res)
61400