題目連結:
題目意譯:
給定一字串 s 代表著一個合法運算式,實作一個基礎的計算機來求出其值,並回傳求值的結果。
注:你不得使用任何可以把字串當作數學運算式求值的內建函式,例如 eval()。
限制:
1 ≦ s.length ≦ 3 * 10 ^ 5
s 由數字、 '+' 、 '-' 、 '(' 、 ')' 和 ' ' 所組成。
s 代表著一個合法的運算式。
'+' 不會被當作一元運算子使用(例,"+1" 和 "+(2 + 3)" 是不合法的)。
'-' 可能會被當作一個一元運算子使用(例,"-1" 和 "-(2 + 3)" 是合法的)。
輸入中不會有兩個運算子接連著出現。
每個數字以及中途之運算將皆可以容納進一個 32 位元有號整數。
範例測資:
範例 1:
輸入: s = "1 + 1"
輸出: 2
範例 2:
輸入: s = " 2-1 + 2 "
輸出: 3
範例 3:
輸入: s = "(1+(4+5+2)-3)+(6+8)"
輸出: 23
解題思維:
不過現在由於 '-' 多了可以當負號的功能。因此,我們可以在原本存運算子、運算元的堆疊(Stack)部分多加一個負責存每個運算元的正負號,然後原本存運算子的堆疊可以不用了(反正本題沒有其他種類的運算子)。
所以現在當我們遇到 '+' 、 '-' 就是先當作它們是正負號的運算。然後之後要做運算時就只需把運算元以及對應的正負號抓出來統一做加法即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。