1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public:
int minOperationsToFlip(string expression) {
vector<pair<int, int>> stack_num;
vector<int> stack_op;
auto op_and = [](int x1, int y1, int x2, int y2) -> pair<int, int> {
return {min({x1 + x2, x1 + y2, x2 + y1}), y1 + y2};
};
auto op_or = [](int x1, int y1, int x2, int y2) -> pair<int, int> {
return {x1 + x2, min({x1 + y2, x2 + y1, x2 + y1, y1 + y2})};
};
auto calc = [&]() {
if (stack_num.size() >= 2 && (stack_op.back() == '|' || stack_op.back() == '&')) {
auto [x1, y1] = stack_num.back(); stack_num.pop_back();
auto [x2, y2] = stack_num.back(); stack_num.pop_back();
auto [x_and, y_and] = op_and(x1, y1, x2, y2);
auto [x_or, y_or] = op_or(x1, y1, x2, y2);
if (stack_op.back() == '&') {
stack_num.emplace_back(min(x_and, x_or + 1), min(y_and, y_or + 1));
} else {
stack_num.emplace_back(min(x_or, x_and + 1), min(y_or, y_and + 1));
}
stack_op.pop_back();
}
};
for (char c : expression) {
if (c == '(' || c == '|' || c == '&') {
stack_op.push_back(c);
} else if (c == '0') {
stack_num.emplace_back(0, 1);
calc();
} else if (c == '1') {
stack_num.emplace_back(1, 0);
calc();
} else {
assert(c == ')');
stack_op.pop_back();
calc();
}
}
return max(stack_num[0].first, stack_num[0].second);
}
};
|