Minimum Cost to Change the Final Value of Expression LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minOperationsToFlip(string exp) {
4
    stack<pair<char, int>> st; // exp val,cost
5

6
    pair<char, int> p;
7

8
    for (auto x : exp) {
9
      if (x == '(' || x == '&' || x == '|') {
10
        st.push({x, 0}); // till now no looking need to change exp so mark cost
11
                         // as 0 or we can add cost of these while solving exp
12
      } else {
13
        if (x == ')') {
14
          p = st.top();
15
          st.pop();
16
          st.pop(); // this pop for '('
17
        } else {
18
          // if number or we can say '0' or '1'
19
          p = {x, 1}; // cost going to be one becoz x if either '0' or '1'
20
        }
21
        while (!st.empty() && (st.top().first == '&' || st.top().first == '|')) {
22
          char op = st.top().first;
23
          st.pop();
24
          char val2 = p.first;
25
          int cost2 = p.second;
26
          char val1 = st.top().first;
27
          int cost1 = st.top().second;
28
          st.pop();
29

30
          if (op == '&') {
31
            if (val1 == '1' && val2 == '1') {
32
              p = {'1', min(cost1, cost2)};
33
            }
34
            if (val1 == '1' && val2 == '0') {
35
              p = {'0', 1};
36
            }
37
            if (val1 == '0' && val2 == '1') {
38
              p = {'0', 1};
39
            }
40
            if (val1 == '0' && val2 == '0') {
41
              p = {'0', min(1 + cost1, 1 + cost2)};
42
            }
43
          }
44

45
          if (op == '|') {
46
            if (val1 == '1' && val2 == '1') {
47
              p = {'1', 1 + min(cost1, cost2)};
48
            }
49
            if (val1 == '1' && val2 == '0') {
50
              p = {'1', 1};
51
            }
52
            if (val1 == '0' && val2 == '1') {
53
              p = {'1', 1};
54
            }
55
            if (val1 == '0' && val2 == '0') {
56
              p = {'0', min(cost1, cost2)};
57
            }
58
          }
59
        }
60
        st.push(p);
61
      }
62
    }
63
    return st.top().second;
64
  }
65
};
66
// code by sachin