Calculator: Given an arithmetic equation consisting of positive integers, +, -, * and / (no parentheses), compute the result.
EXAMPLE
1
2
|
Input : 2*3+5/6*3+15
Output: 23.5
|
Hints: #521, #624, #665, #698
解法
没有括号，这个比较好做。
做两个栈，一个操作数栈，一个操作符栈。
当遇到数字的时候，压入操作数栈。
遇到符号的时候根据情况：
- 如果当前符号优先级 < 栈顶符号，则先【计算】，然后做第2步
- 压入符号到操作数栈
计算过程：
- 从操作符取出一个元素，从操作数取出两个元素
- 将计算结果压入操作数栈中
比如：
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
|
2 + 3 - 5
STEP 1
Operands : [2] // 尾部代表栈顶
Operators: [] // 尾部代表栈顶
STEP 2
Operands : [2]
Operators: [+]
STEP 3
Operands : [2, 3]
Operators: [+]
STEP 4
Operands : [2, 3, 5]
Operators: [+, -]
STEP 5
Operands : [2, -2]
Operators: [+]
STEP 6
Operands : [0]
Operators: []
|
比如：
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
|
2 + 3 * 5
STEP 1
Operands : [2]
Operators: []
STEP 2
Operands : [2]
Operators: [+]
STEP 3
Operands : [2, 3]
Operators: [+]
STEP 4
Operands : [2, 3, 5]
Operators: [+, *]
STEP 5
Operands : [2, 15]
Operators: [+]
STEP 6
Operands : [17]
Operators: []
|
比如：
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
|
2 * 3 + 5
STEP 1
Operands : [2]
Operators: []
STEP 2
Operands : [2]
Operators: [*]
STEP 3
Operands : [2, 3]
Operators: [*]
STEP 4 因为+优先级比*低，所以先把*计算了
Operands : [6]
Operators: [+]
STEP 5
Operands : [6, 5]
Operators: [+]
STEP 6
Operands : [11]
Operators: []
|
代码：
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
|
public double calculate(String expression) {
Stack<Double> operands = new Stack<>();
Stack<Char> operators = new Stack<>();
boolean nextNum = true;
while (expression != "") {
if (nextNum) {
String num = nextNum(expression);
expression = expression.subString(num.length());
nextNum = false;
operands.push(Double.valueOf(num));
} else {
char op = getNextOp(expression);
expression = expression.subString(1);
nextNum = true;
if (!operators.isEmpty()) {
char prevOp = operators.peek();
if (isOpGt(prevOp, op)) {
operands.push(calc(operands, operators));
}
}
operators.push(op);
}
}
// 做最后的计算
while (!operators.isEmpty()) {
operands.push(calc(operands, operators));
}
return operands.pop();
}
private char nextOp(String expression) {
return expression.charAt(0);
}
private String nextNum(String expression) {
int s = 0;
for (int i = 1; i < expression.length(); i++) {
char d = expression.charAt(i);
if (d < '0' || d > '9') {
break;
}
}
return expression.subString(s, i);
}
private double calc(Stack<Double> operands, Stack<Char> operators) {
double b = operands.pop();
double a = operands.pop();
char op = operators.pop();
switch (op) {
case '*':
return a * b;
case '-':
return a - b;
case '+':
return a + b;
case '/':
return a / b;
}
return 0d;
}
private boolean isOpGt(char op1, char op2) {
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) {
return true;
}
return false;
}
|
评论