<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, expr: str) -> int:
        # expr is valid boolean expression with
        #     ()
        #     & |
        #     0 1
        #
        # min cost to change the overall expression result
        # valid changes:
        #    >  swap 1 with 0
        #    >  swap & with |

        # eval in left-right order

        # we can parse with Dijkstra shunting yard, or discount version since all ops have the same precedence |
        # if there's an operator on the stack we eval it asap instead of just evaling higher-prec ops plus handling
        # left/right assoc. issues (hooray for not having to deal with that!!)

        # each stack level thus has 1-2 values and an operator
        # if we have 2 values an an operator, do the eval

        # next up: how do we find the min change?
        # most obvious: try all single-value changes
        # then all two-value changes, etc.
        # wherein we can use BFS and a `seen` set. VERY inefficient though if we can find a clever pattern

        # min cost to change:
        #    suppose we have the tree form of the expression with their current values
        #    nodes are leaves, or operators

        # min cost to switch a 0 to a 1 is
        #   leaf: 0/1 literal: 1 op
        #   operator parent: if it's L & R:
        #      convert L and R from 0 to 1
        #      convert L OR R from 0 to 1 and swap & with |

        # so we can build the overall tree and use DFS to find the cheapest change

        N = len(expr)

        # 1. preliminaries: Node helper class, functions
        class Node:
            def __init__(self, op, val, left, right):
                self.op = op # &, |, or None for a literal 0/1 leaf
                self.value = val
                self.left = left
                self.right = right

            def __repr__(self) -> str:
                return f"Node(op={self.op},value={self.value},..)"

        funcs = {
            '&': (lambda l, r: l.value & r.value), 
            '|': (lambda l, r: l.value | r.value)
        }

        # 2. parse expr to tree form; levels[0][0] will be the overall result at the end
        levels = []
        levels.append([None, None]) # node we've parsed thus far, if any, and a trailing operator

        def handleArgNode(node) -> None:
            # if we did Dijkstra's Shunting Yard we'd
            #    > put node on the stack, so args stack [.., node]
            #    > have an op on the stack, so ops stack [op]
            #    > then popped prior two, combined with op, and pushed it back
            # This is a shortcut to the same thing!

            if levels[-1][0]:
                # a valid expr has a prior node and operator already here, we assume this is valid
                l = levels[-1][0]
                r = node
                op = levels[-1][1]
                result = Node(op, funcs[op](l, r), l, r)

                # this is where most of our simplification of a full Dijkstra's Shunting Yard is done
                levels[-1][0] = result # the equivalent of popping arity, eval, push result
                levels[-1][1] = None # the equivalent of popping and evaluating the top operator in the op stack
            else:
                levels[-1][0] = node

        for i, c in enumerate(expr):
            if c == '(':
                levels.append([None, None])
            elif c == ')':
                # assume valid: should have a node and no trailing operator
                node = levels.pop()[0]
                handleArgNode(node)
            elif c in '01':
                val = int(c)
                node = Node(None, val, None, None)
                handleArgNode(node)
            elif c in '&|':
                # assume valid, that we don't have consec ops somehow
                levels[-1][1] = c
            else:
                raise ValueError(f"Unexpected char {c=} at position {i=}. {levels=}")

        # 3. compute min cost to change the result from a zero to one or vice-versa

        def cost01(node) -> int:
            if node.value == 1: return 0 # already 1

            if node.op is None: return 1 # cost to change a literal is 1: 0 -> 1

            if node.op == '&':
                if node.left.value | node.right.value: return 1 # just change & to |
                else:
                    # can change both children to 1
                    # or change just one child to 1 and change & to |
                    # min cost to change children is 1 each so oneChild plus &->| is at least as good as changing both children
                    return 1 + min(cost01(node.left), cost01(node.right))
            else:
                # |, and value is 0 so we need to promote a child to 1
                return min(cost01(node.left), cost01(node.right))

        def cost10(node) -> int:
            if node.value == 0: return 0

            if node.op is None: return 1

            if node.op == '&':
                # currently 1, so both children must be 1. need to demote a child to 0
                return min(cost10(node.left), cost10(node.right))
            else:
                # |, currently value == 1
                #     if both children 1: can convert both to 0 with at least 2 ops, or convert one to 0 and swap | with &
                #         latter is always at least as good because changing a 1 to 0 costs at least one anyway
                if node.left.value & node.right.value:
                    return 1 + min(cost10(node.left), cost10(node.right))
                else:
                    # one child is a 1
                    # can change that single 1 child to 0 in at least 1 op
                    # or change this node to & for 1 op
                    # latter option is at least as optimal always
                    return 1

        root = levels[0][0]
        
        if root.value == 0:
            return cost01(root)
        else:
            return cost10(root)
28500