实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数,+, - ,*,/ 四种运算符和空格 。整数除法仅保留整数部分。
示例 1:
输入: "3+2*2"
输出: 7
示例 2:
输入: " 3/2 "
输出: 1
示例 3:
输入: " 3+5 / 2 "
输出: 5
答案:
1public int calculate(String s) {
2 int len;
3 if (s == null || (len = s.length()) == 0) return 0;
4 Stack<Integer> stack = new Stack<Integer>();
5 int num = 0;
6 char sign = '+';
7 for (int i = 0; i < len; i++) {
8 if (Character.isDigit(s.charAt(i))) {
9 num = num * 10 + s.charAt(i) - '0';
10 }
11 if ((!Character.isDigit(s.charAt(i)) && ' ' != s.charAt(i)) || i == len - 1) {
12 if (sign == '-') {
13 stack.push(-num);
14 }
15 if (sign == '+') {
16 stack.push(num);
17 }
18 if (sign == '*') {
19 stack.push(stack.pop() * num);
20 }
21 if (sign == '/') {
22 stack.push(stack.pop() / num);
23 }
24 sign = s.charAt(i);
25 num = 0;
26 }
27 }
28 int re = 0;
29 for (int i : stack) {
30 re += i;
31 }
32 return re;
33}
解析:
先把乘除的结果和没有参与计算的值全部存储在堆栈stack中,最后再遍历堆栈的值进行相加即可。比较容易理解,就不再过多介绍,要注意的是加减乘除的混合运算,先算乘除在算加减。还可以换种解法
1public int calculate(String s) {
2 Stack<Integer> stack = new Stack<>();
3 int result = 0;
4 for (int i = 0, num = 0, op = '+'; i < s.length(); i++) {
5 char c = s.charAt(i);
6 if (Character.isDigit(c))
7 num = num * 10 + (c - '0');
8 if ("+-*/".indexOf(c) >= 0 || i == s.length() - 1) {
9 if ("*/".indexOf(op) >= 0)
10 result -= stack.peek();
11 switch (op) {
12 case '+':
13 stack.push(num);
14 break;
15 case '-':
16 stack.push(-num);
17 break;
18 case '*':
19 stack.push(stack.pop() * num);
20 break;
21 case '/':
22 stack.push(stack.pop() / num);
23 break;
24 }
25 num = 0;
26 op = c;
27 result += stack.peek();
28 }
29 }
30 return result;
31}
这种解法和第一种有一点区别,他是直接计算,注意这里的op保存的是上一步操作的符号,第9行如果是乘除法,第10行就会把多加的移除,然后在下面的while循环中进行运算。再来看最后一种解法
1public int calculate(String s) {
2 if (s == null || s.length() == 0) return 0;
3 Stack<Integer> stack = new Stack<>();
4 s += '+';
5 char op = '+';
6 for (int i = 0, n = 0; i < s.length(); i++) {
7 char c = s.charAt(i);
8 if (c >= '0' && c <= '9') {
9 n = n * 10 + c - '0';
10 continue;
11 }
12 if (c == ' ') continue;
13 if (op == '+') stack.push(n);
14 else if (op == '-') stack.push(-n);
15 else if (op == '*') stack.push(stack.pop() * n);
16 else if (op == '/') stack.push(stack.pop() / n);
17 op = c;
18 n = 0;
19 }
20 int total = 0;
21 while (!stack.isEmpty()) total += stack.pop();
22 return total;
23}
这种解法和第一种原理其实都是一样的。