aboutsummaryrefslogtreecommitdiff
path: root/min_cost_change_expr.cpp
blob: c75d10c09bce69e4627ce2a43e13113404bc5abc (plain)
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
#include "leetcode.h"

class Solution {
public:
  int minOperationsToFlip(string expression) {
    vector<vector<array<char, 2>>> vva(1);
    for (auto ch : expression) {
      if (ch == '(')
        vva.push_back(vector<array<char, 2>>());
      else if (ch == ')') {
        auto val = eval(vva.back(), vva.back().size() - 1);
        vva.pop_back();
        vva.back().push_back(val);
      } else
        vva.back().push_back({ch, 1});
    }
    return eval(vva.back(), vva.back().size() - 1)[1];
  }

private:
  array<char, 2> eval(vector<array<char, 2>> &exp, int i) {
    if (i == 0)
      return exp[0];
    auto left = eval(exp, i - 2), right = exp[i];
    int v1 = left[0] - '0', v2 = right[0] - '0', cost = 1;
    if (exp[i - 1][0] == '|') {
      if (v1 == v2)
        cost = min(left[1], right[1]) + (v1 == 1);
      return {v1 | v2 ? '1' : '0', (char)cost};
    }
    if (v1 == v2)
      cost = min(left[1], right[1]) + (v1 == 0);
    return {v1 & v2 ? '1' : '0', (char)cost};
  }
};

int main() {
  Solution obj;
  cout << obj.minOperationsToFlip("(0|(1|0&1))");
}