1 題目描述


這題是 Hard 的題目,難度在於,要如何處理以下問題:

  1. 碰到括號怎麼進行優先處理
  2. 括號前面的“-”號會改變括號內的數字正負,並且要與括號外的數字相加

2 解法

首先一個很重要的概念是,我們要如何處理括號的問題,這邊我們會使用到三個變數:

  1. sign:用來記錄當前的正負號,初始值為 1,通常用來記錄數字前一個符號是正還是負。
  2. res:用來記錄當前的結果,初始值為 0,通常是用來記錄左括號之前的加總數字。
  3. num:用來記錄當前的數字,初始值為 0,通常是當前括號內的數字總和。

因此我們所使用的公式如下:

在了解公式之後,我們要有一個邏輯處理當碰到左括號右括號的流程。
當碰到左括號

  1. 我們要記錄當前的 ressign先放到 stack 裡面,並且重新設定 ressign 為 0 和 1。
  2. 然後優先處理括號內的數字,直到遇到右括號。

當碰到右括號

  1. 當前的 res 是括號內的加總數字
  2. 括號的前一個符號,也就是在 stack 裡面的 sign 會決定括號內的數字是正還是負。
  3. 因此我們會將括號也就是當前的 res 和 stack 的sign 取出來並相乘,再加回去 來自 stack 的 res

流程大概就是這樣,以 (1+(4+5+2)-3)-(16+8) 為例:

  1. 因為一開始就是 (,所以我們會將 ressign 放到 stack 裡面,並且重新設定 ressign 為 0 和 1。
  2. 然後開始處理 1+ 的部分,res 會變成 1,sign 會變成 1。
  3. 結果又碰到 (,所以我們會將 res(1) 和 sign(1) 放到 stack 裡面,並且重新設定 ressign 為 0 和 1。
  4. 開始專心處理 4+5+2 的部分,res 會變成 11,sign 會變成 1。
  5. 結果碰到了 ),這時候我們要將 stack 的 sign pop 出來與括號的 res相乘,並且與 stack 中的 res 相加。
  6. 然後繼續處理…
    (參考以下示意圖)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def calculate2(self, s):
"""
1. Take 3 containers:
num -> to store current num value only
sign -> to store sign value, initially +1
res -> to store sum
When ( comes these containers used for calculate sum of intergers within () brackets.
--------------------
2. When c is + or -
Move num to res, because we need to empty num for next integer value.
set num = 0
sign = update with c
--------------------
3. When c is '('
Here, we need num, res, sign to calculate sum of integers within ()
So, move num and sign to stack => [num, sign]
Now reset - res = 0, num = 0, sign = 1 (default)
--------------------
4. When c is ')' -> 2-(3+4), Here res=3, num=4, sign=1 stack [2, -]
res +=sign*num -> calculate sum for num first, then pop items from stack, res=7
res *=stack.pop() - > Pop sign(+ or -) to multiply with res, res = 7*(-1)
res +=stack.pop() - > Pop integer and add with prev. sum, res = -7 + 2 - 5
--------------------
Simple Example: 2 - 3
Initially res will have 2,i.e. res = 2
then store '-' in sign. it will be used when 3 comes. ie. sign = -1
Now 3 comes => res = res + num*sign
Return statement: res+num*sign => res = 2 + 3(-1) = 2 - 3 = -1
"""
num = 0
sign = 1
res = 0
stack = []
for i in range(len(s)): # iterate till last character
c = s[i]
if c.isdigit(): # process if there is digit
num = num * 10 + int(c) # for consecutive digits 98 => 9x10 + 8 = 98
elif c in '-+': # check for - and + sign,如果沒遇到括號,就繼續計算res總額
res += num * sign
sign = -1 if c == '-' else 1
num = 0
elif c == '(': # if ( comes, 儲存括號以外的總額,與括號之前的符號
stack.append(res)
stack.append(sign)
res = 0 # reset res for new calculation
sign = 1
elif c == ')': # if ) comes, 括號結束的意思,可以把 stack 的內容取出來計算
res += sign * num
res *= stack.pop()
res += stack.pop()
num = 0
return res + num * sign

3 總結

這題真的難,這題的難度我卡在不知道該怎麼處理括號前面對“負號“的狀況,這邊的解法是把括號前面的符號存到 stack 裡面,然後在括號結束的時候,再取出來相乘,這樣就可以處理括號前面的負號問題。