05 August 2008
思路
构建一个 Poly 多项式类，实现这个多项式类的一些数学操作。
算法
单独实现每个方法都很直接，这里先列一下要实现的方法：
Poly:add(this, that) 返回 this + that 的结果。
Poly:sub(this, that) 返回 this - that 的结果。
Poly:mul(this, that) 返回 this * that 的结果。
Poly:evaluate(this, evalmap) 返回将所有的自由变量替换成 evalmap 指定常数之后的结果。
Poly:toList(this) 返回正确的多项式输出格式。
Solution::combine(left, right, symbol) 返回对 左边（left) 和 右边(left) 进行 symobl 操作之后的结果。
Solution::make(expr) 创造一个新的 Poly 实例来表示常数或 expr 指定的变量。
Solution::parse(expr) 将 expr 解析成一个 Poly 实例。
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
class Solution {
public List<String> basicCalculatorIV(String expression, String[] evalVars, int[] evalInts) {
Map<String, Integer> evalMap = new HashMap();
for (int i = 0; i < evalVars.length; ++i)
evalMap.put(evalVars[i], evalInts[i]);
return parse(expression).evaluate(evalMap).toList();
}
public Poly make(String expr) {
Poly result = new Poly();
List<String> list = new ArrayList();
if (Character.isDigit(expr.charAt(0))) {
result.update(list, Integer.valueOf(expr));
} else {
list.add(expr);
result.update(list, 1);
}
return result;
}
public Poly combine(Poly left, Poly right, char symbol) {
if (symbol == '+') return left.add(right);
if (symbol == '-') return left.sub(right);
if (symbol == '*') return left.mul(right);
throw null;
}
public Poly parse(String expr) {
List<Poly> bucket = new ArrayList();
List<Character> symbols = new ArrayList();
int i = 0;
while (i < expr.length()) {
if (expr.charAt(i) == '(') {
int bal = 0, j = i;
for (; j < expr.length(); ++j) {
if (expr.charAt(j) == '(') bal++;
if (expr.charAt(j) == ')') bal--;
if (bal == 0) break;
}
bucket.add(parse(expr.substring(i+1, j)));
i = j;
} else if (Character.isLetterOrDigit(expr.charAt(i))) {
int j = i;
search : {
for (; j < expr.length(); ++j)
if (expr.charAt(j) == ' ') {
bucket.add(make(expr.substring(i, j)));
break search;
}
bucket.add(make(expr.substring(i)));
}
i = j;
} else if (expr.charAt(i) != ' ') {
symbols.add(expr.charAt(i));
}
i++;
}
for (int j = symbols.size() - 1; j >= 0; --j)
if (symbols.get(j) == '*')
bucket.set(j, combine(bucket.get(j), bucket.remove(j+1), symbols.remove(j)));
if (bucket.isEmpty()) return new Poly();
Poly ans = bucket.get(0);
for (int j = 0; j < symbols.size(); ++j)
ans = combine(ans, bucket.get(j+1), symbols.get(j));
return ans;
}
}
class Poly {
HashMap<List<String>, Integer> count;
Poly() {count = new HashMap();}
void update(List<String> key, int val) {
this.count.put(key, this.count.getOrDefault(key, 0) + val);
}
Poly add(Poly that) {
Poly ans = new Poly();
for (List<String> k: this.count.keySet())
ans.update(k, this.count.get(k));
for (List<String> k: that.count.keySet())
ans.update(k, that.count.get(k));
return ans;
}
Poly sub(Poly that) {
Poly ans = new Poly();
for (List<String> k: this.count.keySet())
ans.update(k, this.count.get(k));
for (List<String> k: that.count.keySet())
ans.update(k, -that.count.get(k));
return ans;
}
Poly mul(Poly that) {
Poly ans = new Poly();
for (List<String> k1: this.count.keySet())
for (List<String> k2: that.count.keySet()) {
List<String> kNew = new ArrayList();
for (String x: k1) kNew.add(x);
for (String x: k2) kNew.add(x);
Collections.sort(kNew);
ans.update(kNew, this.count.get(k1) * that.count.get(k2));
}
return ans;
}
Poly evaluate(Map<String, Integer> evalMap) {
Poly ans = new Poly();
for (List<String> k: this.count.keySet()) {
int c = this.count.get(k);
List<String> free = new ArrayList();
for (String token: k) {
if (evalMap.containsKey(token))
c *= evalMap.get(token);
else
free.add(token);
}
ans.update(free, c);
}
return ans;
}
int compareList(List<String> A, List<String> B) {
int i = 0;
for (String x: A) {
String y = B.get(i++);
if (x.compareTo(y) != 0) return x.compareTo(y);
}
return 0;
}
List<String> toList() {
List<String> ans = new ArrayList();
List<List<String>> keys = new ArrayList(this.count.keySet());
Collections.sort(keys, (a, b) ->
a.size() != b.size() ? b.size() - a.size() : compareList(a, b));
for (List<String> key: keys) {
int v = this.count.get(key);
if (v == 0) continue;
StringBuilder word = new StringBuilder();
word.append("" + v);
for (String token: key) {
word.append('*');
word.append(token);
}
ans.add(word.toString());
}
return ans;
}
}
1