306,基本计算器 II

实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数,+, - ,*,/ 四种运算符和空格  。整数除法仅保留整数部分。

示例 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}

这种解法和第一种原理其实都是一样的。

上一篇:打工人都觉得香的Java程序员306道面试秘笈,爆肝


下一篇:PetaPoco 5.1.306 的生成模板加注释