forked from pxu/Algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBasicCalculatorIII.java
More file actions
74 lines (64 loc) · 1.85 KB
/
BasicCalculatorIII.java
File metadata and controls
74 lines (64 loc) · 1.85 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
74
public class BasicCalculatorIII {
public boolean hasPrecedence(char pre_op, char cur_op) {
if(pre_op == '(' || pre_op == ')') return false;
else if((pre_op == '+' || pre_op == '-') && (cur_op == '*' || cur_op == '/')) return false;
return true;
}
public long cal(long x, long y, char op) {
if(op == '+') {
return x + y;
} else if(op == '-') {
return x - y;
} else if(op == '*') {
return x * y;
} else {
return x / y;
}
}
public long eval(String exp) {
if(exp == null || exp.length() == 0) return 0;
char[] ce = exp.toCharArray();
int n = ce.length;
LinkedList<Long> nstack = new LinkedList<Long> ();
LinkedList<Character> opstack = new LinkedList<Character> ();
int i = 0;
while(i < n) {
if(ce[i] == ' ') {
++i;
} else if(ce[i] == '(') {
opstack.addFirst(ce[i]);
++i;
} else if(ce[i] == ')') {
while(!opstack.isEmpty() && opstack.peekFirst() != '(') {
long operand2 = nstack.pollFirst();
long operand1 = nstack.pollFirst();
nstack.addFirst(cal(operand1, operand2, opstack.pollFirst()));
}
opstack.pollFirst();
++i;
} else if(ce[i] >= '0' && ce[i] <= '9') {
StringBuffer sb = new StringBuffer();
while(i < n && (ce[i] >= '0' && ce[i] <= '9')) {
sb.append(ce[i]);
++i;
}
nstack.addFirst(Long.parseLong(sb.toString()));
} else {
char cur_op = ce[i];
while(!opstack.isEmpty() && hasPrecedence(opstack.peekFirst(), cur_op)) {
long operand2 = nstack.pollFirst();
long operand1 = nstack.pollFirst();
nstack.addFirst(cal(operand1, operand2, opstack.pollFirst()));
}
opstack.addFirst(cur_op);
++i;
}
}
while(!opstack.isEmpty()) {
long operand2 = nstack.pollFirst();
long operand1 = nstack.pollFirst();
nstack.addFirst(cal(operand1, operand2, opstack.pollFirst()));
}
return nstack.pollFirst();
}
}