題目描述

這是 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ù)、 )
• let 表達(dá)式采用? "(let v1 e1 v2 e2 ... vn en expr)" 的形式，其中? let 總是以字符串? "let"來表示，接下來會(huì)跟隨一對(duì)或多對(duì)交替的變量和表達(dá)式，也就是說，第一個(gè)變量? v1被分配為表達(dá)式? e1?的值，第二個(gè)變量? v2?被分配為表達(dá)式? e2?的值，依次類推；最終 let 表達(dá)式的值為? expr 表達(dá)式的值。
• add 表達(dá)式表示為? "(add e1 e2)" ，其中? add 總是以字符串? "add" 來表示，該表達(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á)式的值之 積 。
• 在該題目中，變量名以小寫字符開始，之后跟隨 個(gè)或多個(gè)小寫字符或數(shù)字。為了方便， "add" ， "let" ， "mult" 會(huì)被定義為 `"關(guān)鍵字" ，不會(huì)用作變量名。
• 最后，要說一下作用域的概念。計(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 值時(shí)， 在變量的上下文中由最內(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?。

提示：

• 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<String, Integer> map) 函數(shù)，代表計(jì)算 的結(jié)果，答案為 dfs(0,n-1,map)，其中 為字符串的長(zhǎng)度。

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

• 若 ，說明是表達(dá)式，此時(shí)從 開始往后取，取到空格為止（假設(shè)位置為 idx），從而得到操作 op（其中 op 為 let、add 或 mult 三者之一），此時(shí) op 對(duì)應(yīng)參數(shù)為 ，也就是需要跳過位置 （即跳過 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ā)，一直往右找（不超過 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
  

• 否則 不是表達(dá)式，通過判斷 是否有被哈希表記錄來得知結(jié)果：若在哈希表中有記錄，結(jié)果為哈希表中的映射值，否則結(jié)果為本身所代表的數(shù)值。

需要注意，根據(jù)「作用域」的定義，我們不能使用全局哈希表，而要在每一層遞歸時(shí)，傳入 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<String,?Integer>?map)?{
????????if?(cs[l]?==?'(')?{
????????????int?idx?=?l;
????????????while?(cs[idx]?!=?'?')?idx++;
????????????String?op?=?s.substring(l?+?1,?idx);
????????????r--;?//?判別為?"(let"、"(add"?或?"(mult"?后，跳過對(duì)應(yīng)的?")"
????????????if?(op.equals("let"))?{
????????????????for?(int?i?=?idx?+?1;?i?<=?r;?)?{
????????????????????int?j?=?getRight(i,?r);
????????????????????String?key?=?s.substring(i,?j);
????????????????????if?(j?>=?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ù)雜度為
• 空間復(fù)雜度：

最后

這是我們「刷穿 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ù)：https://github.com/SharingSource/LogicStack-LeetCode 。

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

更多更全更熱門的「筆試/面試」相關(guān)資料可訪問排版精美的 合集新基地 ????