-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_224.java
More file actions
73 lines (68 loc) · 2.51 KB
/
Copy pathP_224.java
File metadata and controls
73 lines (68 loc) · 2.51 KB
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
package leetcode.hard;
import java.util.ArrayDeque;
import java.util.Collections;
import java.util.Deque;
public class P_224 {
public int calculateImproved(String s) {
final Deque<Integer> dq = new ArrayDeque<>(Collections.singletonList(1));
final char[] w = s.toCharArray();
int res = 0;
int sign = 1;
int num = 0;
for (char c : w) {
if (c >= '0' && c <= '9') {
num = num * 10 + (c - '0');
} else if (c == '+' || c == '-') {
res += sign * num;
sign = dq.getFirst() * (c == '+' ? 1 : -1);
num = 0;
} else if (c == '(') {
dq.addFirst(sign);
} else if (c == ')') {
dq.removeFirst();
}
}
res += sign * num;
return res;
}
public int calculate(String s) {
final Deque<Deque<Integer>> terms = new ArrayDeque<>(Collections.singletonList(new ArrayDeque<>()));
final Deque<Deque<Character>> signs = new ArrayDeque<>(Collections.singletonList(new ArrayDeque<>()));
final char[] chars = s.toCharArray();
int idx = 0;
while (idx < chars.length) {
if (chars[idx] == '(') {
terms.addFirst(new ArrayDeque<>());
signs.addFirst(new ArrayDeque<>());
} else if (Character.isDigit(chars[idx])) {
int num = chars[idx] - '0';
while (++idx < chars.length && Character.isDigit(chars[idx])) {
num *= 10;
num += chars[idx] - '0';
}
idx--;
terms.getFirst().offerLast(num);
} else if (chars[idx] == '+' || chars[idx] == '-') {
signs.getFirst().offerLast(chars[idx]);
} else if (chars[idx] == ')') {
final int res = evaluate(terms, signs);
terms.removeFirst();
signs.removeFirst();
terms.getFirst().offerLast(res);
}
idx++;
}
return evaluate(terms, signs);
}
private static int evaluate(Deque<Deque<Integer>> terms, Deque<Deque<Character>> signs) {
int res = terms.getFirst().removeFirst();
while (!terms.getFirst().isEmpty()) {
if (signs.getFirst().removeFirst() == '+') {
res += terms.getFirst().removeFirst();
} else {
res -= terms.getFirst().removeFirst();
}
}
return res;
}
}