題目描述

這是 LeetCode 上的 736. Lisp 語(yǔ)法解析 ，難度為 困難。

Tag : 「DFS」、「模擬」、「哈希表」

給你一個(gè)類似 Lisp 語(yǔ)句的字符串表達(dá)式 expression，求出其計(jì)算結(jié)果。

表達(dá)式語(yǔ)法如下所示:

• 表達(dá)式可以為整數(shù)，let 表達(dá)式，add 表達(dá)式，mult 表達(dá)式，或賦值的變量。表達(dá)式的結(jié)果總是一個(gè)整數(shù)。
• (整數(shù)可以是正整數(shù)、負(fù)整數(shù)、000)
• let 表達(dá)式采用 “(let v1 e1 v2 e2 … vn en expr)” 的形式，其中 let 總是以字符串 “let”來(lái)表示，接下來(lái)會(huì)跟隨一對(duì)或多對(duì)交替的變量和表達(dá)式，也就是說(shuō)，第一個(gè)變量 v1被分配為表達(dá)式 e1 的值，第二個(gè)變量 v2 被分配為表達(dá)式 e2 的值，依次類推；最終 let 表達(dá)式的值為 expr 表達(dá)式的值。
• add 表達(dá)式表示為 “(add e1 e2)” ，其中 add 總是以字符串 “add” 來(lái)表示，該表達(dá)式總是包含兩個(gè)表達(dá)式 e1、e2 ，最終結(jié)果是 e1 表達(dá)式的值與 e2 表達(dá)式的值之 和 。
• mult 表達(dá)式表示為 “(mult e1 e2)” ，其中 mult 總是以字符串 “mult” 表示，該表達(dá)式總是包含兩個(gè)表達(dá)式 e1、e2，最終結(jié)果是 e1 表達(dá)式的值與 e2 表達(dá)式的值之 積 。
• 在該題目中，變量名以小寫字符開始，之后跟隨 000 個(gè)或多個(gè)小寫字符或數(shù)字。為了方便，”add” ，”let” ，”mult” 會(huì)被定義為 `”關(guān)鍵字” ，不會(huì)用作變量名。
• 最后，要說(shuō)一下作用域的概念。計(jì)算變量名所對(duì)應(yīng)的表達(dá)式時(shí)，在計(jì)算上下文中，首先檢查最內(nèi)層作用域（按括號(hào)計(jì)），然后按順序依次檢查外部作用域。測(cè)試用例中每一個(gè)表達(dá)式都是合法的。有關(guān)作用域的更多詳細(xì)信息，請(qǐng)參閱示例。

示例 1：

輸入：expression = “(let x 2 (mult x (let x 3 y 4 (add x y))))” 輸出：14 解釋： 計(jì)算表達(dá)式 (add x y), 在檢查變量 x 這是， 在變量的上下文中由最內(nèi)層作用域依次向外檢查。 首先找到 x = 3, 所以此處的 x 只是 3 。 示例 2：

輸入：expression = “(let x 3 x 2 x)”輸出：2解釋：let 語(yǔ)句中的賦值運(yùn)算按順序處理即可。

示例 3：

輸入：expression = “(let x 1 y 2 x (add x y) (add x y))”輸出：5解釋：第一個(gè) (add x y) 計(jì)算結(jié)果是 3，并且將此值賦給了 x 。 第二個(gè) (add x y) 計(jì)算結(jié)果是 3 + 2 = 5 。

提示：

• 1<=expression.length<=20001 <= expression.length <= 20001<=expression.length<=2000
• exprssion 中不含前導(dǎo)和尾隨空格
• expressoin 中的不同部分（token）之間用單個(gè)空格進(jìn)行分隔
• 答案和所有中間計(jì)算結(jié)果都符合 32-bit 整數(shù)范圍

DFS 模擬

今天身體不舒服，不寫太詳細(xì)，題目不難，大家結(jié)合代碼看吧。

設(shè)計(jì)函數(shù) int dfs(int l, int r, Map map) 函數(shù)，代表計(jì)算 s[l…r]s[l…r]s[l…r] 的結(jié)果，答案為 dfs(0,n-1,map)，其中 nnn 為字符串的長(zhǎng)度。

根據(jù)傳入的 [l,r][l, r][l,r] 是否為表達(dá)式分情況討論：

• 若 s[l]=(s[l] = (s[l]=(，說(shuō)明是表達(dá)式，此時(shí)從 lll 開始往后取，取到空格為止（假設(shè)位置為 idx），從而得到操作 op（其中 op 為 let、add 或 mult 三者之一），此時(shí) op 對(duì)應(yīng)參數(shù)為 [idx+1,r 1][idx + 1, r – 1][idx+1,r 1]，也就是需要跳過(guò)位置 rrr（即跳過(guò) op 對(duì)應(yīng)的 ) 符號(hào)）；
• 再根據(jù) op 為何種操作進(jìn)一步處理，我們?cè)O(shè)計(jì)一個(gè)「?jìng)魅胱蠖它c(diǎn)找右端點(diǎn)」的函數(shù) int getRight(int left, int end)，含義為從 left 出發(fā)，一直往右找（不超過(guò) end），直到取得合法的「子表達(dá)式」或「對(duì)應(yīng)的值」。
• // 對(duì)于 getRight 函數(shù)作用，給大家舉個(gè) 理解吧，其實(shí)就是從 left 出發(fā)，找到合法的「子表達(dá)式」或「值」為止 // (let x 2 (mult x (let x 3 y 4 (add x y)))) // a b // 傳入 a 返回 b，代表 [a, b) 表達(dá)式為 (mult x (let x 3 y 4 (add x y))) // (let x 2 (mult x (let x 3 y 4 (add x y)))) // ab // 傳入 a 返回 b，代表 [a, b) 表達(dá)式為 x
• 否則 s[l…r]s[l…r]s[l…r] 不是表達(dá)式，通過(guò)判斷 s[l…r]s[l…r]s[l…r] 是否有被哈希表記錄來(lái)得知結(jié)果：若在哈希表中有記錄，結(jié)果為哈希表中的映射值，否則結(jié)果為本身所代表的數(shù)值。

需要注意，根據(jù)「作用域」的定義，我們不能使用全局哈希表，而要在每一層遞歸時(shí)，傳入 clone 出來(lái)的 map。

代碼：

class Solution { char[] cs; String s; public int evaluate(String _s) { s = _s; cs = s.toCharArray(); return dfs(0, cs.length – 1, new HashMap()); } int dfs(int l, int r, Map map) { if (cs[l] == ‘(‘) { int idx = l; while (cs[idx] != ‘ ‘) idx++; String op = s.substring(l + 1, idx); r–; // 判別為 “(let”、”(add” 或 “(mult” 后，跳過(guò)對(duì)應(yīng)的 “)” if (op.equals(“let”)) { for (int i = idx + 1; i = r) return dfs(i, j – 1, new HashMap(map)); j++; i = j; j = getRight(i, r); int value = dfs(i, j – 1, new HashMap(map)); map.put(key, value); i = j + 1; } return -1; // never } else if (op.equals(“add”)) { int j = getRight(idx + 1, r); int a = dfs(idx + 1, j – 1, new HashMap(map)), b = dfs(j + 1, r, new HashMap(map)); return a + b; } else { int j = getRight(idx + 1, r); int a = dfs(idx + 1, j – 1, new HashMap(map)), b = dfs(j + 1, r, new HashMap(map)); return a * b; } } else { String cur = s.substring(l, r + 1); if (map.containsKey(cur)) return map.get(cur); return Integer.parseInt(cur); } } int getRight(int left, int end) { int right = left, score = 0; while (right <= end) { if (cs[right] == '(') { score++; right++; } else if (cs[right] == ')') { score–; right++; } else if (cs[right] == ' ') { if (score == 0) break; right++; } else { right++; } } return right; }}

• 時(shí)間復(fù)雜度：除對(duì)表達(dá)式進(jìn)行遞歸劃分以外，還存在對(duì) map 的每層拷貝操作，復(fù)雜度為 O(n2)O(n^2)O(n2)
• 空間復(fù)雜度：O(n)O(n)O(n)

最后

這是我們「刷穿 LeetCode」系列文章的第 No.736 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們將先把所有不帶鎖的題目刷完。

在這個(gè)系列文章里面，除了講解解題思路以外，還會(huì)盡可能給出最為簡(jiǎn)潔的代碼。如果涉及通解還會(huì)相應(yīng)的代碼模板。

為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼，我建立了相關(guān)的倉(cāng)庫(kù)：github.com/SharingSour… 。

在倉(cāng)庫(kù)地址里，你可以看到系列文章的題解鏈接、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和其他優(yōu)選題解。

原文鏈接：https://juejin.cn/post/7117155612231729160