题目描述

实现一个计算器支持+、-、*、/、（、)等，需要支持括号嵌套。

示例 1：

1
2
输入：s = 1*2-3*5*8/4+3
输出：-25

示例 2：

1
2
输入：s = 12*4-25+6/(2+(2-1)*2-1)-4*3
输出：13

示例 3：

1
2
输入：s = 12*4-(25+6/(2+(2-1)*2-1)-4*3)
输出：33

示例 4：

1
2
输入：s = 12*4/2-(25+6/(2+(2-1)*2-1)-4*3)
输出：9

我的解法

思路

此题与leetcode题库中的 面试题 16.26. 计算器 非常类似，不同的是此题需要处理嵌套的括号。一个比较普遍的思路就是首先处理括号，将整个表达式转换为没有括号的算式，再进行计算。

我们使用栈记录已经遍历的字符，当遇到第一个右括号时，说明是第一个嵌套最深的括号，我们依次弹出元素，直到遇到与其匹配的左括号，计算后，再次压入栈中。重复以上步骤，便可处理掉所有括号，接下来再计算算式。

代码

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
class Solution {

    public int calculate(String s) {
        LinkedList<String> s1 = new LinkedList<>();
        // 处理括号
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c != ')') {
                s1.addLast(String.valueOf(c));
                continue;
            }
            StringBuilder sb = new StringBuilder();
            while (!s1.isEmpty() && !"(".equals(s1.getLast())) {
                sb.append(s1.removeLast());
            }
            s1.removeLast();
            s1.addLast(String.valueOf(calculateNormal(sb.reverse().toString())));
        }
        // 去掉括号之后的算式
        StringBuilder sb = new StringBuilder();
        s1.forEach(sb::append);
        return calculateNormal(sb.toString());
    }


    private int calculateNormal(String s) {
        int num = 0;
        char preSign = '+';
        LinkedList<Integer> stack = new LinkedList<>();
        // 处理+ - * /
        for (int i = 0; i < s.length(); ++i) {
            boolean digit = Character.isDigit(s.charAt(i));
            if (digit) {
                num = num * 10 + s.charAt(i) - '0';
            }
            if (!digit || i == s.length() - 1) {
                switch (preSign) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    default:
                        stack.push(stack.pop() / num);
                }
                preSign = s.charAt(i);
                num = 0;
            }
        }
        return (int) stack.stream().mapToInt(x -> x).summaryStatistics().getSum();
    }

}

测试

添加测试用例：

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
class Test {
    String S;
    int Expect;

    public Test(String s, int expect) {
        this.S = s;
        this.Expect = expect;
    }
}

public class Main {

    public static void main(String[] args) {
        Solution solution = new Solution();
        Test[] testList = new Test[]{
                new Test("1*2-3*5*8/4+3", 1 * 2 - 3 * 5 * 8 / 4 + 3),
                new Test("12*4-25+6/(2+(2-1)*2-1)-4*3", 12 * 4 - 25 + 6 / (2 + (2 - 1) * 2 - 1) - 4 * 3),
                new Test("12*4-(25+6/(2+(2-1)*2-1)-4*3)", 12 * 4 - (25 + 6 / (2 + (2 - 1) * 2 - 1) - 4 * 3)),
                new Test("12*4/2-(25+6/(2+(2-1)*2-1)-4*3)", 12 * 4 / 2 - (25 + 6 / (2 + (2 - 1) * 2 - 1) - 4 * 3)),
        };
        for (Test test : testList) {
            int calculate = solution.calculate(test.S);
            System.out.println((calculate == test.Expect) + "------>" + calculate);
        }
    }

}

运行启动类，查看控制台：

1
2
3
4
true------>-25
true------>13
true------>33
true------>9