05 August 2008
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, 1
+
1
-
1
*
1
/
Example 1:
1
2
Input: "3+2*2"
Output: 7
Example 2:
1
2
Input: " 3/2 "
Output: 1
Example 3:
1
2
Input: " 3+5 / 2 "
Output: 5
Note:
1
eval
设计一个计算器，输入一个有效的字符串表达式，加减乘除后输出一个整数，除法是地板除法，表达式里的数字都是正整数。eval()是脚本语言中的方法，Java并没有。
相对于Basic Calculate I中只有加减，这道题多了乘除，因为没有括号，所以简化了。使用stack来存储计算的中间结果，每次遇到加减法就直接压入；遇到乘除法就先计算一下再压入。
时间上一遍扫过去O(n)，空间上开了一个stack，O(n)。
当然这道题不用stack也可以（不如stack直观），可以把string先转换成char array，然后从左到右运算，维持一个result负责最终结果和一个pre负责遇到乘法除法的时候重算一下先做乘除。复杂度同stack。
Stack
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
class Solution {
public int calculate(String s) {
if (s.isEmpty()) {
return 0;
}
int num = 0;
int len = s.length();
Stack<Integer> stack = new Stack<>();//存符号两边的数字
char sign = '+';
for (int i = 0; i < len; i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
num = num * 10 + (ch - '0'); //多位数的多个数字
}
if ((!Character.isDigit(ch) && //不是数字，是符号
ch != ' ') || //不是空格
i == len - 1) { //最后一个位置虽然是数字但位置特殊也要计算
// 加法和减法是直接push，加正数和负数的区别
if (sign == '+') {
stack.push(num);
}
if (sign == '-') {
stack.push(-num);
}
//乘法和除法是先计算两旁的数再push
if (sign == '*') {
stack.push(stack.pop() * num); //stack中最顶上的数字是当前符号的前一个数字
}
if (sign == '/') {
stack.push(stack.pop() / num);
}
sign = ch; //更新当前sign的符号，下一次循环根据sign的值处理该sign两边的数字
num = 0;
}
}
int result = 0;
//循环做完后，所有乘法和除法也做完并push了，目前stack里面只剩加法和减法符号
for (int ele : stack) { //这样遍历是先进先出（顺序不影响）
result += ele;
}
return result;
}
}
用变量来维持
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
class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int result = 0, previous = 0, num = 0;
char sign = '+';
char[] array = s.trim().toCharArray();
for (int i = 0; i <= array.length; i++) {//<=表示最后还得运算一次
if (i != array.length && Character.isDigit(array[i])) {
num = num * 10 + array[i] - '0';
} else {
if (i != array.length && array[i] == ' ') {
continue;
}
if (sign == '+') {
result += num;
previous = num;
}
if (sign == '-') {
result -= num;
previous = -num;
}
if (sign == '*') {
result = result - previous + previous * num;//之前多加了一次num，因为之前不知道后面的运算符，所以先加了这里再减了再做乘法
previous = previous * num;//乘法运算符两边的数相乘为下一轮当前数的previous
}
if (sign == '/') {
result = result - previous + previous / num;
previous = previous / num;
}
num = 0;
if (i != array.length) {
sign = array[i];
}
}
}
return result;
}
}