題目描述

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

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

給你一個類似 Lisp 語句的字符串表達式 expression，求出其計算結果。

表達式語法如下所示:

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

示例 1：

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

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

示例 3：

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

提示：

• 1<=expression.length<=20001 <= expression.length <= 20001<=expression.length<=2000
• exprssion 中不含前導和尾隨空格
• expressoin 中的不同部分（token）之間用單個空格進行分隔
• 答案和所有中間計算結果都符合 32-bit 整數范圍

DFS 模擬

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

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

根據傳入的 [l,r][l, r][l,r] 是否為表達式分情況討論：

• 若 s[l]=(s[l] = (s[l]=(，說明是表達式，此時從 lll 開始往后取，取到空格為止（假設位置為 idx），從而得到操作 op（其中 op 為 let、add 或 mult 三者之一），此時 op 對應參數為 [idx+1,r 1][idx + 1, r – 1][idx+1,r 1]，也就是需要跳過位置 rrr（即跳過 op 對應的 ) 符號）；
• 再根據 op 為何種操作進一步處理，我們設計一個「傳入左端點找右端點」的函數 int getRight(int left, int end)，含義為從 left 出發(fā)，一直往右找（不超過 end），直到取得合法的「子表達式」或「對應的值」。
• // 對于 getRight 函數作用，給大家舉個 理解吧，其實就是從 left 出發(fā)，找到合法的「子表達式」或「值」為止 // (let x 2 (mult x (let x 3 y 4 (add x y)))) // a b // 傳入 a 返回 b，代表 [a, b) 表達式為 (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) 表達式為 x
• 否則 s[l…r]s[l…r]s[l…r] 不是表達式，通過判斷 s[l…r]s[l…r]s[l…r] 是否有被哈希表記錄來得知結果：若在哈希表中有記錄，結果為哈希表中的映射值，否則結果為本身所代表的數值。

需要注意，根據「作用域」的定義，我們不能使用全局哈希表，而要在每一層遞歸時，傳入 clone 出來的 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” 后，跳過對應的 “)” 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; }}

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

最后

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

在這個系列文章里面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模板。

為了方便各位同學能夠電腦上進行調試和提交代碼，我建立了相關的倉庫：github.com/SharingSour… 。

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

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