#54381: 從無括號到有括號的思路


chiuliyou@gmail.com (邱立宇)


先不去考慮有括號的情況,假設當前運算式是7 + 10 + 14 * 4 - 8 / 7 * 42。
建立兩個stack,一個nums計入數字,一個oper計入運算符號。
1. 一開始遇到數字7、+、10、+、14、*
  - nums = [7, 10, 14]
  - oper = [+, +, *]
2. 這時棧頂符號是*,因為先乘除後加減,下個數字4跟棧頂數字14相乘後,再放到棧中。並繼續操作
  - nums = [7, 10, 56, 8]
  - oper = [+, +, -, /]
3. 棧頂符號是/,同樣的道理,下個數字5跟棧頂數字8相除。
  - nums = [7, 10, 56, 1.14]
  - oper = [+, +, -, *]
4. 棧頂符號*,下個數字42跟棧頂數字1.14相乘。
  - nums = [7, 10, 56, 48]
  - oper = [+, +, -]
5. 讀完運算式,現在需要從左到右計算,否則在遇到1-1+1的情況,先結合右邊的做法會出錯。
  - return 7 + 10 + 56 - 48。
由於除法會將小數位砍掉,最後程式輸出 31。

假如在運算式當中加入了括號,比如7 + (10 + (14 * 4 - 8) / 7) * 42(空格只是方便看,實際上相連)
我們能用遞迴的方式,將有括號情況簡化成沒有括號的情況。
定義dfs(i)代表從位置i為起點,計算運算式的結果。
1. dfs(0),一開始加入數字7與+
  - nums = [7]
  - oper = [+]
2. 遇到左括號,遞迴呼叫dfs(3),在dfs(3)當中
  - nums = [10]
  - oper = [+]
  1. 遇到左括號,遞迴呼叫dfs(8),計算14 * 4 - 8
    - 遇到右括號,代表遞迴結束,回傳計算結果48
    - 為了讓dfs(3)知道return時計算到哪,用變數where紀錄計算位置。where = 13(括號位置)
  根據where得知還沒計算到底,從where繼續往下走,直到遇到右括號或是結尾。
  - nums = [10, 48, 7]->[10, 6.85]->[16.85]
  - oper = [+, /]->[+]->[]
  回傳16.85,此時where = 16。
3. dfs(0)收到遞迴呼叫結果。
  - nums = [7, 16.85]
  - oper = [+]
  根據where得知還沒計算到底,從where繼續往下走,直到遇到右括號或是結尾。
  - nums = [7, 16.85, 42]
  - oper = [+, *]
  計算最後結果,得到714.7。

程式碼:https://gjplieqszy7.sg.larksuite.com/wiki/KJC1wRJAqidzAqkpCEClyp2YgUf#share-ZCFXdRYowoJK0SxCkJBlURHogUf