'1','0','&','|','(', and ')'

All parentheses are properly matched.

There will be no empty parentheses (i.e: "()" is not a substring of expression).

Solution

Method 1 – Dynamic Programming with Stack

Intuition

We parse the expression recursively, keeping track of the minimum cost to flip the result to 0 or 1 at each subexpression. For each operator, we combine the costs from its left and right children according to the operator's logic, and use a stack to handle parentheses.

Approach

Use a stack to parse the expression and evaluate subexpressions.
For each operand ('0' or '1'), store the cost to make it 0 and 1.
For each operator ('&' or '|'), combine the costs from left and right:
- For '&':
  - To get 1: both sides must be 1.
  - To get 0: either side can be 0.
- For '|':
  - To get 0: both sides must be 0.
  - To get 1: either side can be 1.
For each subexpression, store the minimum cost to make it 0 and 1.
At the end, return the cost to flip the final value.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minOperationsToFlip(string expr) {\n        stack<pair<int,int>> stk;\n        stack<char> ops;\n        auto merge = [](pair<int,int> a, pair<int,int> b, char op) {\n            if (op == '&') {\n                int to1 = a.second + b.second;\n                int to0 = min(a.first, b.first);\n                if (a.first == b.first) to0++;\n                return make_pair(to0, to1);\n            } else {\n                int to0 = a.first + b.first;\n                int to1 = min(a.second, b.second);\n                if (a.second == b.second) to1++;\n                return make_pair(to0, to1);\n            }\n        };\n        for (char c : expr) {\n            if (c == '0') stk.push({0,1});\n            else if (c == '1') stk.push({1,0});\n            else if (c == '(') ops.push(c);\n            else if (c == ')') {\n                while (ops.top() != '(') {\n                    auto b = stk.top(); stk.pop();\n

Related Tags