LC上有非常多很括號(hào)相關(guān)的問(wèn)題届慈。比如說(shuō)有一類是純括號(hào)判斷判斷一個(gè)STRING里的括號(hào)是否合法润匙，或者要加最少多少個(gè)括號(hào)可以使得它合法琅关，或者移除最少多少個(gè)括號(hào)使得它合法等革骨。
另外一類是基于括號(hào)會(huì)有一些運(yùn)算至朗，比如說(shuō)2（XXX） = XXXXXX 這種decode模式的題目屉符。這個(gè)專題我會(huì)介紹2個(gè)這類問(wèn)題的本質(zhì)，幫助你在下次閱讀到這類問(wèn)題锹引，知道如何從本質(zhì)去思考矗钟，然后快速找到問(wèn)題的突破點(diǎn)。

本質(zhì)1：括號(hào)合法匹配的本質(zhì)嫌变，就是在一個(gè)字符串任意前綴里吨艇，他的左括號(hào)數(shù)量必須都大于等于右括號(hào)數(shù)量。然后最終的字符串左括號(hào)數(shù)量和右括號(hào)數(shù)量相等腾啥。

本質(zhì)2 : 括號(hào)求表達(dá)式的本質(zhì)东涡，每一個(gè)括號(hào)內(nèi)部是一個(gè)子問(wèn)題冯吓，我們可以直接把子問(wèn)題交給遞歸假設(shè)它已解決，然后只要思考如何匯總子問(wèn)題的解變成全局的解的方法疮跑。

1.括號(hào)合法匹配的本質(zhì)

有了本質(zhì)1的特性组贺，我們?cè)倌嫦蛩伎迹裁磿r(shí)候括號(hào)不合法祖娘，就可以解決一大類問(wèn)題了失尖。不合法無(wú)非2種。1. 右括號(hào)多余左括號(hào)了渐苏。 2. 到最后左括號(hào)還多出了一些掀潮，沒(méi)有被右括號(hào)關(guān)掉

那么只要維護(hù)這2個(gè)不合法信息，我就可以知道括號(hào)是否合法琼富。
我們只要在遇到做左括號(hào)時(shí)對(duì)L++胧辽，右括號(hào)時(shí)對(duì)L--。一旦發(fā)現(xiàn)L<0了公黑，就代表右括號(hào)多出來(lái)了邑商。到最后L！=0就代表左括號(hào)沒(méi)被關(guān)掉凡蚜。

上面是個(gè)基礎(chǔ)技能人断。

我們?cè)僭诨A(chǔ)技能上去衍生一下，看一個(gè)不合法的括號(hào)情況朝蜘，如果加上最少的括號(hào)使得它合法恶迈。這個(gè)其實(shí)很好想，就是對(duì)每一個(gè)不合法的括號(hào)（分為兩類谱醇，中間多出來(lái)的右括號(hào)暇仲，和最后沒(méi)關(guān)掉的左括號(hào)）

LC. 921 題 就引刃而解

public int minAddToMakeValid(String S) {
        char[] cs = S.toCharArray();
        int l = 0, r = 0;
        for (char c : cs) {
            if (c == '(') {
                l++;
            } else if (l > 0) {
                l--;
            } else r++;
        }
        return l + r;
    }

下面我們來(lái)看一道對(duì)偶題。最少移除括號(hào)的問(wèn)題
是LC 1249. Minimum Remove to Make Valid Parentheses

如果只是要求數(shù)量的話副渴，上面的代碼原封不動(dòng)就可以用奈附。
這里面需要求一個(gè)具體解。這個(gè)時(shí)候煮剧，就要求我們要移除正確的括號(hào)了斥滤。 如果上面那題增加括號(hào)也要一個(gè)具體解，小伙伴們想想如何改
其實(shí)這邊也很好想勉盅，凡是要R++的地方佑颇，我就跳過(guò)這個(gè)字母。就解決了中間多出來(lái)的右括號(hào)問(wèn)題草娜。然后從后往前再掃一次挑胸，凡是遇到左括號(hào)，我就直接去掉宰闰。就一定可以把沒(méi)關(guān)掉的左括號(hào)給關(guān)掉了茬贵。

這里有些讀者會(huì)問(wèn)為什么不可以從左往右的凸克。為什么一定要從右往左呢？

這是因?yàn)槊屏ぃ阋菑淖笸铱赡苁强梢晕剑部赡苁且瞥艘粋€(gè)合法右括號(hào)的左半邊，引入了新的不合法右括號(hào)比如
()(, 你要是從左移除可能會(huì)變成)(

那為什么從右往左沒(méi)這個(gè)問(wèn)題呢舆逃？
這里有2個(gè)思考角度

• 第一個(gè)角度就是蚂维，因?yàn)樗杏依ㄌ?hào)前必然已經(jīng)有一個(gè)左括號(hào)了。還多出來(lái)一些左括號(hào)路狮，一定是要么在所有右括號(hào)后面虫啥。那么從右往左就可以WORK，如果是在合法右括號(hào)左邊奄妨。比如((),那么即使你移走了一個(gè)左括號(hào)穆壕，前面多出來(lái)的左括號(hào)也可以立刻補(bǔ)位铝噩。

• 如果有另一個(gè)平行宇宙矮固，括號(hào)是這樣使用的)(, 那么我們就可以在那個(gè)平行宇宙 用規(guī)則1 去先把多出來(lái)的右括號(hào)( 給刪去蝇刀。這時(shí)就是想只要怎么把這個(gè)宇宙的括號(hào)規(guī)則給映射去那個(gè)宇宙，其實(shí)就是reverse一下就可以

舉個(gè)例子( () () ( reverse一下 變成( )( )( (, 記住這個(gè)時(shí)候(是那個(gè)宇宙的右括號(hào)了直焙。我們套用規(guī)則1景东，可以發(fā)現(xiàn)第一個(gè)和最后一個(gè) 是多出來(lái)的右括號(hào)。去掉之后合法括號(hào)為)( )(
那么本質(zhì)這邊就是在原宇宙從右向左掃描奔誓。

上面那道題代碼就如下所示

public String minRemoveToMakeValid(String s) {
        char[] cs = s.toCharArray();
        int l = 0, idx = 0;
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] == '(') {
                l++;
            } else if (cs[i] == ')') {
                if (l == 0) continue;
                l--;
            }
            cs[idx++] = cs[i];
        }
        int j = cs.length - 1, len = idx - l;
        for (int i = idx - 1; i >= 0; i--) {
            if (l > 0 && cs[i] == '(') l--;
            else cs[j--] = cs[i];
        }
       return new String(cs, j + 1, len);
    }

如果我要最少移除括號(hào)的所有可能解斤吐，應(yīng)該如何求呢

我們之前找了數(shù)量，然后找了任一解厨喂，下面問(wèn)題如果是所有解和措，應(yīng)該怎么求呢？
這就是一道LC HARD問(wèn)題了蜕煌。

是LC 301. Remove Invalid Parentheses
https://leetcode.com/problems/remove-invalid-parentheses/

這道題其實(shí)本質(zhì)還是找所有可以刪除的括號(hào)
我們一開(kāi)始先把不合法的左括號(hào)數(shù)量和 右括號(hào)的數(shù)量用之前的套路給統(tǒng)計(jì)出來(lái)派阱。
如果有不合法右括號(hào)，就一定要先從左到向刪右括號(hào)幌绍。因?yàn)樵谟依ㄌ?hào)被刪干凈前颁褂，左括號(hào)一定是不夠的。不然就不會(huì)出現(xiàn)不合法的右括號(hào)傀广，所以在前面刪左括號(hào)是沒(méi)必要的。等右括號(hào)刪干凈了彩届。然后之前跳到最后嘗試刪左括號(hào)伪冰。
因?yàn)榇鸢敢ブ兀杂羞B續(xù)K個(gè)相同格式的括號(hào)的情況下只看第一個(gè)樟蠕。這是基本的去重思路了贮聂。當(dāng)然偷懶可以用SET來(lái)去重靠柑。

List<String> res = new ArrayList<>();
    public List<String> removeInvalidParentheses(String s) {
        char[] cs = s.toCharArray();
        // 統(tǒng)計(jì)左右括號(hào)不合法數(shù)量, l代表左括號(hào)不合法數(shù)量，r代表右括號(hào)不合法數(shù)量
        int l = 0, r = 0;
        for (int i = 0; i < cs.length; i++) {
            char c = cs[i];
            if (c == '(') {
                l++;
            } else if (c == ')') {
                if (l > 0) l--;
                else r++;
            }
        }
        dfs(cs, 0, cs.length - 1, l, r, (char)0);
        return new ArrayList<>(res);
    }
    void dfs(char[] cs, int st, int ed, int l, int r, char pre) {
        if (l == 0 && r == 0) {
            String valid = valid(cs);
            if (valid != null)
                res.add(valid);
            return;
        }
        if (st > ed) return;
        if (r > 0) {
            char cur = cs[st];
            if (cur == ')' && pre != ')') {
                cs[st] = 0;
                dfs(cs, st + 1, ed, l, r - 1, cs[st]);
            }
            cs[st] = cur;
            dfs(cs, st + 1, ed, l, r, cur);
        } else { // l > 0
            char cur = cs[ed];
            if (cur == '(' && pre != '(') {
                cs[ed] = 0;
                dfs(cs, st, ed - 1, l - 1, r, cs[ed]);
            }
            cs[ed] = cur;
            dfs(cs, st, ed - 1, l, r, cur);
        }
    }
// 合法的返回結(jié)果字符串吓懈，不然返回null
    String valid(char[] cs) {
        StringBuilder sb = new StringBuilder();
        int l = 0;
        for (char c : cs) {
            if (c == 0) continue;
            sb.append(c);
            if (c == '(') l++;
            else if (c == ')') {
                if (--l < 0) return null;
            }
        }
        return l > 0 ? null : sb.toString();
    }

當(dāng)然我們用角度2去寫(xiě)這個(gè)題也是可以的
思路為先考慮右括號(hào)不合法歼冰，再反向考慮左括號(hào)不合法。當(dāng)遇到一個(gè)右括號(hào)不合法耻警，我們需要枚舉之前所有的右括號(hào)依次去掉都是解隔嫡。
然后考慮左括號(hào)，可以用平行世界法甘穿。

List<String> res = new ArrayList<>();
public List<String> removeInvalidParentheses(String s) {
    dfs(s, 0, '(', ')');
    return res;
}
void dfs(String ans, int lastJ, char L, char R) {
    int l = 0;
    for (int i = 0; i < ans.length(); i++) {
        char c  = ans.charAt(i);
        if (c == L) l++;
        else if (c == R) l--;
        if (l >= 0) continue;
// 枚舉之前所有的右括號(hào)依次去掉
        for (int j = lastJ; j <= i; j++) {
            if (ans.charAt(j) == R && (j == lastJ || ans.charAt(j - 1) != R))
                dfs(ans.substring(0, j) + ans.substring(j + 1), j, L, R);
        }
        return;
    }
    String rev = new StringBuilder(ans).reverse().toString();
    if (L == '(') dfs(rev,0, R, L); // 去平行宇宙
    else res.add(rev);
}

最后我們來(lái)看另一道HARD題腮恩，
是LC. 32. Longest Valid Parentheses

這道題，就是要求一個(gè)最長(zhǎng)的合法括號(hào)匹配子串温兼。根據(jù)我們的定義知道秸滴，只要遇到了不合法的右括號(hào)，那么就要和之前的字符串做一個(gè)了斷了募判。因?yàn)橹灰诉@個(gè)前綴就不會(huì)再合法荡含。那么根據(jù)前面的MAX來(lái)跟前全局的MAX。之后從頭開(kāi)始届垫。

下一個(gè)問(wèn)題是内颗，如果滿足了沒(méi)有任何前綴有多出來(lái)的右括號(hào)，我怎么知道這個(gè)前綴中最長(zhǎng)的合法子串是多少長(zhǎng)呢敦腔。
所謂合法就是意味著還要滿足第二個(gè)條件均澳，左右括號(hào)數(shù)量相等。那么我們就需要特判一下這個(gè)條件符衔。

另一個(gè)棘手問(wèn)題是找前，當(dāng)左括號(hào)>右括號(hào)時(shí)，我們不知道后面還有沒(méi)有右括號(hào)可以閉起來(lái)判族。這樣就會(huì)造成一旦之前有個(gè)多出來(lái)的左括號(hào)躺盛，第二個(gè)條件始終沒(méi)法滿足。但是去掉這個(gè)多出來(lái)的左括號(hào)形帮，是可以造成后面滿足條件的槽惫。解決這個(gè)問(wèn)題，就是從右向左再找一遍辩撑，就可以規(guī)避掉最前面的左括號(hào)搗亂了界斜。這時(shí)就是個(gè)平行宇宙的概念。

代碼如下

public int longestValidParentheses(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        return Math.max(help(s, '(', ')'), help(rev, ')', '('));
    }
    int help(String s, char L, char R) {
        int leftCnt = 0, rightCnt = 0, res = 0;
        for (char c : s.toCharArray()) {
            if (c == L) leftCnt++;
            else rightCnt++;
            if (leftCnt == rightCnt) res = Math.max(res, 2 * leftCnt);
            else if (rightCnt > leftCnt) {
                rightCnt = leftCnt = 0;
            }
        }
        return res;
    }

LC上還有一道題是帶通配符的括號(hào)是否匹配

LC 678. Valid Parenthesis String合冀。

其實(shí)就是說(shuō)*既可以被當(dāng)做左括號(hào)或者右括號(hào)或者空白字符各薇。看這個(gè)字符串是否匹配君躺。
其實(shí)本質(zhì)就是在維護(hù)括號(hào)匹配的2大特性峭判。如果當(dāng)中出現(xiàn)了右括號(hào)不合法开缎，我們就看之前的通配符用作左括號(hào)。如果最后是左括號(hào)多出來(lái)了林螃，我們就維護(hù)一個(gè)變量奕删，盡可能壓縮之前的左括號(hào)。
所以我們就有了一個(gè)容錯(cuò)區(qū)間疗认，LMIN是防止左括號(hào)用不完的情況所以代表完残，只要左括號(hào)多出來(lái)了，我來(lái)一個(gè)通配符我都當(dāng)它是右括號(hào)侮邀。 LMAX代表坏怪，希望左括號(hào)越多越好，這樣萬(wàn)一后面來(lái)了很多右括號(hào)绊茧，我也有很多儲(chǔ)備盡可能不被擊穿铝宵。

public boolean checkValidString(String s) {
    int lmax = 0, lmin = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') {
            lmax++; lmin++;
        } else if (c == ')') {
            lmax--; 
            lmin = Math.max(0, lmin - 1);
            if (lmax < 0) return false; // 儲(chǔ)備也被右括號(hào)擊穿了，就徹底不合法
        } else { // 通配符华畏，提升儲(chǔ)備同時(shí)防止左括號(hào)過(guò)多
            lmax++;
            lmin = Math.max(0, lmin - 1);
        }
    }
    return lmin == 0; // 盡可能的消耗左括號(hào)還是消耗不完鹏秋，不合法
}

2.括號(hào)求表達(dá)式的本質(zhì)

在講這個(gè)問(wèn)題之前，我們先來(lái)思考一個(gè)非常簡(jiǎn)單的問(wèn)題亡笑，就是求二叉樹(shù)的深度侣夷。一般二叉樹(shù)的問(wèn)題，很多都可以用遞歸來(lái)解決仑乌。我們?cè)谒伎嫉臅r(shí)候百拓，就是讓左子樹(shù)返回一些信息，同時(shí)讓右子樹(shù)范圍一些信息晰甚。父節(jié)點(diǎn)就根據(jù)左右子樹(shù)返回的信息做一些處理衙传，再返回。這就是二叉樹(shù)里遞歸的思想厕九。

其實(shí)在解決一些表達(dá)式計(jì)算的時(shí)候蓖捶，是和二叉樹(shù)遞歸有很多類似的地方”庠叮基本都可以轉(zhuǎn)換過(guò)去俊鱼。而思維的突破點(diǎn)就是如果定義葉子節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)如何根據(jù)葉子結(jié)算得到值返回給上層畅买。這2個(gè)思考點(diǎn)并闲。

我們來(lái)看一道題
LC. 856. Score of Parentheses
這道題，其實(shí)() 就是葉子節(jié)點(diǎn)皮获，他的分?jǐn)?shù)為1分焙蚓。
內(nèi)部節(jié)點(diǎn)其實(shí)就是外層的括號(hào)，他的函數(shù)就是對(duì)他的孩子節(jié)點(diǎn)返回的值求和 然后再乘以2.
所以一個(gè)這樣的表達(dá)式可以畫(huà)成如下的樹(shù)((()())())
這里整個(gè)表達(dá)式 是個(gè)根節(jié)點(diǎn)洒宝。

image.png

public int scoreOfParentheses(String S) {
    int depth = 0, res = 0;
    char[] cs = S.toCharArray();
    for (int i = 0; i < cs.length; i++) {
        if (cs[i] == '(') depth++;
        else {
            depth--;
            if (cs[i - 1] == '(') 
                res += 1 << depth; // 葉子節(jié)點(diǎn)父能，把父親們積累的DEPTH一次作用上
        }
    }
    return res;
}

有了這個(gè)思路神凑，我們?cè)賮?lái)看另2道題。
一道是394. Decode String
另一道是1190. Reverse Substrings Between Each Pair of Parentheses
在這類題目里何吝，葉子節(jié)點(diǎn)就是括號(hào)里面不帶括號(hào)的STRING溉委。而外層的括號(hào)，就是內(nèi)部節(jié)點(diǎn)爱榕。在第一題中瓣喊，我們可以構(gòu)建的樹(shù)長(zhǎng)成下圖。

我們以2[b2[c]]3[a]為例子

image.png

在第二個(gè)問(wèn)題里
我們以(u(love)i)為例子

image.png

在這類問(wèn)題里黔酥，我們可以使用一個(gè)stack,然后用后序遍歷的方式來(lái)計(jì)算藻三。因?yàn)槊總€(gè)節(jié)點(diǎn)最后返回的是一個(gè)STRING，所以我們可以在STACK里存的是STRINGBUILDER跪者，那么返回的時(shí)候TOSTRING即可棵帽。
當(dāng)我們遇到一個(gè)左括號(hào)，我們推入棧一個(gè)STRINGBUILDER坑夯，然后之后的操作就是在棧頂?shù)腟TRINGBUILDER里做岖寞，直到遇到右括號(hào)，然后把STRINGBUILDER 彈出之后柜蜈，就是在父節(jié)點(diǎn)那層獲得了孩子節(jié)點(diǎn)做完的返回的信息仗谆，然后加入到父節(jié)點(diǎn)的STRINGBUILDER（在棧頂了）中計(jì)算。
所以2道題差不多淑履，代碼如下
第一題對(duì)每個(gè)節(jié)點(diǎn)隶垮，除了要維護(hù)STRING，還要維護(hù)乘法系數(shù)秘噪，所以需要2個(gè)棧

public String decodeString(String s) {
    char[] cs = s.toCharArray();
    Deque<Integer> nums = new ArrayDeque<>();
    Deque<StringBuilder> sbs = new ArrayDeque<>();
    sbs.push(new StringBuilder());
    int num = 0;
    StringBuilder sb = new StringBuilder();
    for (char c : cs) {
        if (c == '[') {
            nums.push(num);
            sbs.push(new StringBuilder());
            num = 0;
        } else if (c == ']') {
            int cnt = nums.pop();
            String cur = sbs.pop().toString();
            for (int i = 0; i < cnt; i++) {
                sbs.peek().append(cur);
            }
        } else if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');
        } else {
            sbs.peek().append(c);
        }
    }
    return sbs.peek().toString();
}

第二題就是出棧的時(shí)候需要做一個(gè)REVERSE

public String reverseParentheses(String s) {
        Deque<StringBuilder> stk = new ArrayDeque<>();
        stk.push(new StringBuilder());
        for (char c : s.toCharArray()) {
            if (c == '(') stk.push(new StringBuilder());
            else if (c == ')') {
                String res = stk.pop().reverse().toString();
                stk.peek().append(res);
            } else stk.peek().append(c);
        }
        return stk.peek().toString();
    }

第二題有一個(gè)O(N)的解法狸吞，由于解法和本章無(wú)關(guān)，所以沒(méi)有介紹，有興趣的小伙伴可以去DISCUSS里學(xué)習(xí)蹋偏。

上面的題目便斥，節(jié)點(diǎn)的定義和節(jié)點(diǎn)的計(jì)算都是比較簡(jiǎn)單直觀的。一般LC HARD的題威始，就會(huì)稍微復(fù)雜一些枢纠。我找到了如下3題。

726. Number of Atoms
727. Parse Lisp Expression
728. Brace Expansion II

對(duì)726題來(lái)說(shuō)
每一個(gè)括號(hào)里我們需要統(tǒng)計(jì)元素的個(gè)數(shù)黎棠，所以需要返回一個(gè)MAP作為信息晋渺，返回到上層后，還需要乘以系數(shù)脓斩，加入父節(jié)點(diǎn)的MAP里木西。因?yàn)樽詈笮枰凑兆帜感蚺判颍允褂肨REEMAP即可随静。

public String countOfAtoms(String formula) {
        Map<String, Integer> m = help(formula.toCharArray());
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            sb.append(e.getKey());
            if (e.getValue() > 1) sb.append(e.getValue());
        }
        return sb.toString();
    }
    int i = 0;
    private Map<String, Integer> help(char[] cs) {
        Map<String, Integer> m = new TreeMap<>();
        while (i < cs.length) {
            if (cs[i] == '(') {
                i++;
                // 拿孩子節(jié)點(diǎn)的信息
                Map<String, Integer> chd = help(cs);
                // 拿系數(shù)
                int num = 0;
                while (i < cs.length && Character.isDigit(cs[i])) num = num * 10 + cs[i++] - '0';
                for (Map.Entry<String, Integer> e : chd.entrySet()) {
                    String key = e.getKey(); 
                    int val = num * e.getValue();
                    m.compute(key, (k,v)->{
                        if (v == null) return val;
                        return v + val;
                    });
                }
            } else if (cs[i] == ')') {
                i++;
                break; // 本節(jié)點(diǎn)MAP處理完畢
            } else {
                // 處理子葉子節(jié)點(diǎn)
                StringBuilder sb = new StringBuilder(""+cs[i++]);
                while (i < cs.length && cs[i] >= 'a' && cs[i] <= 'z') 
                    sb.append(cs[i++]);
                int num = 0;
                while (i < cs.length && Character.isDigit(cs[i])) num = num * 10 + cs[i++] - '0';
                int val = Math.max(1, num);
                m.compute(sb.toString(), (k,v)->{
                    if (v == null) return val;
                    return v + val;
                });
            }
        }
        return m;
    }

我們?cè)賮?lái)看736題
736題對(duì)于一個(gè)樹(shù)節(jié)點(diǎn)來(lái)說(shuō)八千，就是用括號(hào)括起來(lái)的運(yùn)算，里面可能包括子運(yùn)算挪挤。最后返回的是一個(gè)整數(shù)叼丑。節(jié)點(diǎn)有3種類型分別是ADD, MULT, LET。
而葉子節(jié)點(diǎn)就是一個(gè)純數(shù)字扛门。為什么這么定義呢鸠信？因?yàn)槲覀儼l(fā)現(xiàn)5 和 （add 2 3）是可以等價(jià)的。所以純數(shù)字是可以定義為葉子節(jié)點(diǎn)论寨。
然后進(jìn)一步分析星立，ADD, MULT是內(nèi)部節(jié)點(diǎn)的時(shí)候，會(huì)有2個(gè)孩子葬凳。而LET可能有多個(gè)孩子绰垂。
如果內(nèi)部節(jié)點(diǎn)是LET，其之后的結(jié)構(gòu)必然是一個(gè)變量加一個(gè)子節(jié)點(diǎn)火焰。（子節(jié)點(diǎn)可能是葉子節(jié)點(diǎn)劲装，可能是需要遞歸計(jì)算的內(nèi)部節(jié)點(diǎn)），最后一個(gè)子節(jié)點(diǎn)為L(zhǎng)ET的返回值昌简。同時(shí)上層LET的變量表需要透?jìng)鞯狡浜⒆庸?jié)點(diǎn)中占业。
所以大概的樹(shù)結(jié)構(gòu)如下
以(let x 2 (mult x (let x 3 y 4 (add x y))))為例

image.png

public int evaluate(String exp) {
    // hashmap 需要下傳
    return eval(exp, new HashMap<>());
}
private int eval(String exp, Map<String, Integer> vals) {
    // 如果沒(méi)有以括號(hào)開(kāi)頭，那么是葉子節(jié)點(diǎn)
    if (exp.charAt(0) != '(') {
        if (exp.charAt(0) == '-' || Character.isDigit(exp.charAt(0))) { // 純數(shù)字
            return Integer.parseInt(exp);
        } else { // 變量值
            return vals.get(exp);
        }
    }
    // 以括號(hào)開(kāi)頭纯赎，處理內(nèi)部節(jié)點(diǎn)谦疾，后面操作后的參數(shù)按照空格切割。
    List<String> exps = parse(exp);
    // 繼承父親的MAP犬金，構(gòu)建自己這層的MAP
    Map<String, Integer> curVals = new HashMap<>(vals);
    if (exp.startsWith("(a")) { // 如果是加法念恍，遞歸2個(gè)孩子
        return eval(exps.get(0), curVals) + eval(exps.get(1), curVals);
    } else if (exp.startsWith("(m")) { // 如果是乘法六剥，遞歸2個(gè)孩子
        return eval(exps.get(0), curVals) * eval(exps.get(1), curVals);
    } else { // 如果是LET，遞歸（SIZE / 2） 個(gè)孩子
        for (int i = 1; i < exps.size() - 1; i += 2) {
            curVals.put(exps.get(i - 1), eval(exps.get(i), curVals));
        }
        // 最后一個(gè)作為返回值
        return eval(exps.get(exps.size() - 1), curVals);
    }
}
List<String> parse(String curExp) {
    int st = curExp.startsWith("(m") ? 6 : 5;
    curExp = curExp.substring(st);
    char[] cs = curExp.toCharArray();
    int left = 1, i = 0, pre = 0;
    List<String> res = new ArrayList<>();
    for (;left > 0; i++) { // 只關(guān)心本層的括號(hào) 和直接變量峰伙； 遇到上層括號(hào)疗疟，循環(huán)退出
        if (cs[i] == '(') left++;
        else if (cs[i] == ')') { 
            if (left-- == 1) res.add(curExp.substring(pre, i));
        } else if (left == 1 && cs[i] == ' ') {
            res.add(curExp.substring(pre, i));
            pre = i + 1;
        }
    }
    return res;
}

最后一道題1096

我們可以把{}里的值當(dāng)做內(nèi)部節(jié)點(diǎn)，純字母當(dāng)做葉子節(jié)點(diǎn)词爬。
然后內(nèi)部節(jié)點(diǎn)返回的是LIST<STRING>秃嗜， 那么純字母返回的其實(shí)就是只含一個(gè)STRING的LIST权均。
在外層父節(jié)點(diǎn)顿膨，根據(jù)孩子節(jié)點(diǎn)的信息做計(jì)算。
父節(jié)點(diǎn)可以做2種運(yùn)算叽赊，distinct union或者對(duì)2個(gè)集合做笛卡爾乘積恋沃。這取決于節(jié)點(diǎn)之間是否有逗號(hào)。
那么構(gòu)建樹(shù)必指，如下圖
以"{{a,z},a{b,c},{ab,z}}"為例

image.png

int i = 0;
public List<String> braceExpansionII(String expression) {
    String e = "{" + expression + "}";
    return help(e.toCharArray());
}
List<String> help(char[] cs) {
    assert cs[i++] == '{';
    List<List<String>> pre = new ArrayList<>();
    TreeSet<String> set = new TreeSet<>();
    while (i < cs.length) {
        if (cs[i] == ',') {
            // 求之前進(jìn)預(yù)備隊(duì)列的笛卡爾積，然后放進(jìn)DISTINCT UNION
            set.addAll(combine(pre));
            pre = new ArrayList<>();
            i++;
        } else if (cs[i] == '{') {
             // 把孩子的返回桌吃，放進(jìn)笛卡爾積預(yù)備隊(duì)列里
            pre.add(help(cs));
        } else if (cs[i] == '}') break;
        else {
            // 葉子節(jié)點(diǎn)
            StringBuilder sb = new StringBuilder();
            while (Character.isLowerCase(cs[i])) {
                sb.append(cs[i++]);
            }
            pre.add(Arrays.asList(sb.toString()));
        }
    }
    assert cs[i++] == '}';
    // 最后把余下的預(yù)備隊(duì)列里的數(shù)計(jì)算完朱沃，放進(jìn)DISTINCT UNION中
    set.addAll(combine(pre));
    return new ArrayList<>(set);
}
private List<String> combine(List<List<String>> in) {
    List<String> res = Arrays.asList("");
    for (List<String> i: in) {
        List<String> tmp = res;
        res = new ArrayList<>();
        for (String pre : tmp) {
            for (String post : i) {
                res.add(pre + post);
            }
        }
    }
    return res;
}

總結(jié)

今天我們主要講解了2種括號(hào)的套路和思維方式。

• 第一種就是依靠括號(hào)匹配2個(gè)特性來(lái)找到突破點(diǎn)去解題茅诱。特性1是任意前綴左括號(hào)數(shù)量大于右括號(hào)逗物，特性2最終左括號(hào)右括號(hào)數(shù)量相等。
• 第二種就是定義出葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)的計(jì)算單元让簿，找出每個(gè)單元的返回的數(shù)據(jù)結(jié)構(gòu)敬察，然后思考如何利用孩子的解取組合出父親的解。

最后給大家留一道思考題尔当。之前我們只討論了一種括號(hào)的合法匹配莲祸。如果括號(hào)有3種蹂安，{},[],()。 且前者可以包含后者锐帜，后者不能包含前者田盈，如果判斷括號(hào)是匹配的呢。如果不匹配最少刪除多少個(gè)使之匹配呢缴阎？