基本计算器 [括号匹配的变形]

前言

发现括号匹配问题–求解基本表达式 / 对化学表达式的元素计数等相关问题，就像是扁平化嵌套列表一样，本质处理方式都是对树的前序遍历过程。经典括号匹配，掌握其递归匹配 & 栈模拟匹配，才能深刻理解括号匹配的递归性质，而且考究栈帧里面存什么东西？该如何运作？

一、基本计算器

二、栈 & DFS

1、递归遍历每一层括号

// 基本计算器。
public class Calculate {
    /*
    target:给定加减括号空格，把其当作表达式处理。
    只有加减法，没有优先级，碰到括号才会产生优先级，此时递归返回下一层的值即可。

    总：属于括号匹配型，栈 | dfs进行匹配即可，每个括号里的内容当作一个整体。
    除此之外，觉得特别像 扁平化嵌套列表，本质是将树展开，将叶子节点的值累加即可。
     */

    public int calculate(String s) {
        // 先去掉无意义的空字符串。
        this.str = s.replace(" ", "");
        // dfs将每个括号里的内容看成一个整体进行计算。
        return dfs();
    }

    private int dfs() {
        int r = 0;// 该层括号的总和。

        char ch = ' ';
        int pre = 0;// 将 ‘+’ ‘-’号进行抽象，0代表‘-’；1代表‘+’；
        // 碰到末尾，或者‘)’，则表示递归结束，该层计算完毕。
        while (idx < str.length() && ch != ')') {
            ch = str.charAt(idx++);
            // 碰到左括号，将里面的整体进行dfs累加。
            if (ch == '(') {
                int v = dfs();

                r += pre == 0 ? v : -v;
            }
            // 确定符号。
            if (ch == '-') pre = 1;
            if (ch == '+') pre = 0;
            // 整数，可抽象成叶子节点，将其加起来。
            if (Character.isDigit(ch)) {
                int v = getNum(ch - '0');

                r += pre == 0 ? v : -v;
            }
        }

        return r;
    }

    private int getNum(int n) {
        // 10倍扩容法。
        while (idx < str.length() && Character.isDigit(str.charAt(idx)))
            n = n * 10 + str.charAt(idx++) - '0';

        return n;
    }

    // 经典字符串括号匹配，一个字符串，一个下标。
    String str;
    int idx;

}
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

2、栈帧的内容的选择

// 除了dfs，也可进行栈模拟，入栈元素应该是一层的关键消息，入一个累计总和的整数即可。
class Calculate2 {
    /*
    target:给定加减括号空格，把其当作表达式处理。
    只有加减法，没有优先级，碰到括号才会产生优先级，此时递归返回下一层的值即可。

    总：属于括号匹配型，栈 | dfs进行匹配即可，每个括号里的内容当作一个整体。
    除此之外，觉得特别像 扁平化嵌套列表，本质是将树展开，将叶子节点的值累加即可。
     */

    public int calculate(String s) {
        // 先去掉无意义的空字符串。
        this.str = s.replace(" ", "");
        // 每层阔号一个栈帧，如一个Integer即可。
        // 由于需要记录括号前的正负号，所以将Integer变为int[]数组，一个记录该层和，一个记录记下来的符号（抽象）。
        Stack<int[]> sk = new Stack<>();
        sk.push(new int[]{0, 0});

        while (idx < str.length()) {
            char ch = str.charAt(idx++);
            // 确定符号。
            if (ch == '-') sk.peek()[1] = 1;
            if (ch == '+') sk.peek()[1] = 0;
            // 碰到左括号，则需要入栈一个total。
            if (ch == '(') sk.push(new int[]{0, 0});
            // 碰到右括号，则将顶部栈帧和第二层进行融合。
            if (ch == ')') {
                int[] top = sk.pop();
                int[] peek = sk.peek();

                peek[0] += peek[1] == 0 ? top[0] : -top[0];
            }
            // 碰到数字，直接融合到顶部栈帧中，并修改符号。
            if (Character.isDigit(ch)) {
                int v = getNum(ch - '0');
                int[] peek = sk.peek();

                peek[0] += peek[1] == 0 ? v : -v;
            }
        }
        return sk.pop()[0];
    }



    private int getNum(int n) {
        // 10倍扩容法。
        while (idx < str.length() && Character.isDigit(str.charAt(idx)))
            n = n * 10 + str.charAt(idx++) - '0';

        return n;
    }

    // 经典字符串括号匹配，一个字符串，一个下标。
    String str;
    int idx;

}
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

总结

1）括号匹配问题，本质就是递归结构，像树一样，可递归匹配；除此之外，需要的关键信息进行压栈，对这种递归结构会有更深的理解。

2）栈帧里面存入什么？必须存入每层都需要的关键信息，一次dfs就压一次栈，一次dfs结束，就出一次栈。

参考文献

[1] LeetCode 基本计算器

[2] LeetCode 原子的数量 (化学元素求值)

[3] 原子的数量 题解记录

[4] LeetCode 扁平化嵌套列表迭代器

[5] 扁平化嵌套列表迭代器 题解记录