Basic Calculator IV LeetCode solution in Java

1
class Solution {
2
  class Node {
3
    Map<List<String>, Integer> mem = new HashMap<>();
4

5
    void update(List<String> cur, int cnt) {
6
      Collections.sort(cur);
7
      mem.put(cur, mem.getOrDefault(cur, 0) + cnt);
8
    }
9

10
    Node add(Node cur) {
11
      Node ans = new Node();
12
      for (List<String> key1 : mem.keySet()) {
13
        ans.update(key1, mem.get(key1));
14
      }
15
      for (List<String> key2 : cur.mem.keySet()) {
16
        ans.update(key2, cur.mem.get(key2));
17
      }
18
      return ans;
19
    }
20

21
    Node sub(Node cur) {
22
      Node ans = new Node();
23
      for (List<String> key1 : mem.keySet()) {
24
        ans.update(key1, mem.get(key1));
25
      }
26
      for (List<String> key2 : cur.mem.keySet()) {
27
        ans.update(key2, -cur.mem.get(key2));
28
      }
29
      return ans;
30
    }
31

32
    Node mul(Node cur) {
33
      Node ans = new Node();
34
      for (List<String> key1 : mem.keySet()) {
35
        for (List<String> key2 : cur.mem.keySet()) {
36
          List<String> next = new ArrayList<>();
37
          next.addAll(key1);
38
          next.addAll(key2);
39
          ans.update(next, mem.get(key1) * cur.mem.get(key2));
40
        }
41
      }
42
      return ans;
43
    }
44

45
    Node evaluate(Map<String, Integer> vars) {
46
      Node ans = new Node();
47
      for (List<String> cur : mem.keySet()) {
48
        int cnt = mem.get(cur);
49
        List<String> free = new ArrayList<>();
50
        for (String tmp : cur) {
51
          if (vars.containsKey(tmp)) {
52
            cnt = cnt * vars.get(tmp);
53
          } else {
54
            free.add(tmp);
55
          }
56
        }
57
        ans.update(free, cnt);
58
      }
59

60
      return ans;
61
    }
62

63
    List<String> toList() {
64
      List<String> ans = new ArrayList<>();
65
      List<List<String>> keys = new ArrayList<>(mem.keySet());
66
      Collections.sort(
67
          keys,
68
          (List<String> a, List<String> b) -> {
69
            if (a.size() != b.size()) {
70
              return b.size() - a.size();
71
            }
72
            for (int i = 0; i < a.size(); i++) {
73
              if (a.get(i).compareTo(b.get(i)) != 0) {
74
                return a.get(i).compareTo(b.get(i));
75
              }
76
            }
77
            return 0;
78
          });
79

80
      for (List<String> key : keys) {
81
        if (mem.get(key) == 0) {
82
          continue;
83
        }
84
        String cur = "" + String.valueOf(mem.get(key));
85
        for (String data : key) {
86
          cur += "*";
87
          cur += data;
88
        }
89
        ans.add(cur);
90
      }
91
      return ans;
92
    }
93
  }
94

95
  Node make(String cur) {
96
    Node ans = new Node();
97
    List<String> tmp = new ArrayList<>();
98
    if (Character.isDigit(cur.charAt(0))) {
99
      ans.update(tmp, Integer.valueOf(cur));
100
    } else {
101
      tmp.add(cur);
102
      ans.update(tmp, 1);
103
    }
104
    return ans;
105
  }
106

107
  int getNext(String expression, int start) {
108
    int end = start;
109
    while (end < expression.length() && Character.isLetterOrDigit(expression.charAt(end))) {
110
      end++;
111
    }
112
    return end - 1;
113
  }
114

115
  int getPriority(char a) {
116
    if (a == '+' || a == '-') {
117
      return 1;
118
    } else if (a == '*') {
119
      return 2;
120
    }
121
    return 0;
122
  }
123

124
  Node helper(Stack<Node> nums, Stack<Character> ops) {
125
    Node b = nums.pop();
126
    Node a = nums.pop();
127
    char op = ops.pop();
128
    if (op == '*') {
129
      return a.mul(b);
130
    } else if (op == '+') {
131
      return a.add(b);
132
    }
133
    return a.sub(b);
134
  }
135

136
  public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
137
    List<String> ans = new ArrayList<>();
138
    if (expression == null || expression.length() == 0 || evalvars == null || evalints == null) {
139
      return ans;
140
    }
141

142
    Map<String, Integer> vars = new HashMap<>();
143
    for (int i = 0; i < evalvars.length; i++) {
144
      vars.put(evalvars[i], evalints[i]);
145
    }
146

147
    int n = expression.length();
148
    Stack<Node> nums = new Stack<>();
149
    Stack<Character> ops = new Stack<>();
150
    for (int i = 0; i < n; i++) {
151
      char a = expression.charAt(i);
152
      if (Character.isLetterOrDigit(a)) {
153
        int end = getNext(expression, i);
154
        String cur = expression.substring(i, end + 1);
155
        i = end;
156
        Node now = make(cur);
157
        nums.add(now);
158
      } else if (a == '(') {
159
        ops.add(a);
160
      } else if (a == ')') {
161
        while (ops.peek() != '(') {
162
          nums.add(helper(nums, ops));
163
        }
164
        ops.pop();
165
      } else if (a == '+' || a == '-' || a == '*') {
166
        while (ops.size() > 0 && getPriority(ops.peek()) >= getPriority(a)) {
167
          nums.add(helper(nums, ops));
168
        }
169
        ops.add(a);
170
      }
171
    }
172

173
    while (ops.size() > 0) {
174
      nums.add(helper(nums, ops));
175
    }
176

177
    return nums.peek().evaluate(vars).toList();
178
  }
179
}