1
class Solution {
2
  int eval(int a, int b, char op) {
3
    if (op == '+') {
4
      return a + b;
5
    } else {
6
      return a * b;
7
    }
8
  }
9

10
  unordered_map<string_view, unordered_set<int>> mp;
11
  unordered_set<int> potential;
12

13
  unordered_set<int> &solve(string_view s) {
14
    if (auto it = mp.find(s); it != mp.end()) {
15
      return it->second;
16
    }
17

18
    bool res = true;
19
    int n = 0;
20
    unordered_set<int> ans;
21
    for (int i = 0; i < s.size(); i++) {
22
      char c = s[i];
23
      if (c >= '0' && c <= '9') {
24
        n = n * 10 + (c - '0');
25
      } else {
26
        n = 0;
27
        res = false;
28
        for (int l : solve(s.substr(0, i))) {
29
          for (int r : solve(s.substr(i + 1))) {
30
            int res2 = eval(l, r, c);
31
            if (res2 <= 1000) {
32
              ans.insert(res2);
33
            }
34
          }
35
        }
36
      }
37
    }
38
    if (res) {
39
      ans.insert(n);
40
    }
41
    return mp[s] = ans;
42
  }
43

44
 public:
45
  int scoreOfStudents(string s, vector<int> &answers) {
46
    int ans = 0, correct = 0;
47
    stack<int> ns, op;
48
    unordered_map<char, int> prec{{'+', 1}, {'*', 2}, {'(', 0}};
49
    int n = 0;
50
    for (int i = 0; i < s.size(); i++) {
51
      char c = s[i];
52
      if (c >= '0' && c <= '9') {
53
        n = n * 10 + (c - '0');
54
      } else if (c == '(') {
55
        op.push(c);
56
      } else if (c == ')') {
57
        ns.push(n);
58
        while (op.top() != '(') {
59
          int b = ns.top();
60
          ns.pop();
61
          int a = ns.top();
62
          ns.pop();
63
          ns.push(eval(a, b, op.top()));
64
          op.pop();
65
        }
66
        op.pop();
67
        n = ns.top();
68
        ns.pop();
69
      } else {
70
        ns.push(n);
71
        n = 0;
72
        int p = prec[c];
73
        while (!op.empty() && prec[op.top()] >= p) {
74
          int b = ns.top();
75
          ns.pop();
76
          int a = ns.top();
77
          ns.pop();
78
          ns.push(eval(a, b, op.top()));
79
          op.pop();
80
        }
81
        op.push(c);
82
      }
83
    }
84
    ns.push(n);
85
    while (!op.empty()) {
86
      int b = ns.top();
87
      ns.pop();
88
      int a = ns.top();
89
      ns.pop();
90
      ns.push(eval(a, b, op.top()));
91
      op.pop();
92
    }
93
    correct = ns.top();
94

95
    string_view sv{s.data(), s.size()};
96
    solve(sv);
97
    for (int n2 : mp[sv]) {
98
      potential.insert(n2);
99
    }
100

101
    for (int n2 : answers) {
102
      if (n2 == correct) {
103
        ans += 5;
104
      } else if (potential.find(n2) != potential.end()) {
105
        ans += 2;
106
      }
107
    }
108
    return ans;
109
  }
110
};