likes
comments
collection
share

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

作者站长头像
站长
· 阅读数 33

前言

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

一、基本计算器

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

二、栈 & 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;

}

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)栈帧里面存入什么?必须存入每层都需要的关键信息,一次dfs就压一次栈,一次dfs结束,就出一次栈。

参考文献

[1] LeetCode 基本计算器

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

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

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

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