---
# System prepended metadata

title: 224\. Basic Calculator

---

# 224\. Basic Calculator

Clarification:
-   `1 <= s.length <= 3 * 105`
-   `s` consists of digits, `'+'`, `'-'`, `'('`, `')'`, and `' '`.
-   `s` represents a valid expression.
-   `'+'` is **not** used as a unary operation (i.e., `"+1"` and `"+(2 + 3)"` is invalid).
-   `'-'` could be used as a unary operation (i.e., `"-1"` and `"-(2 + 3)"` is valid).
-   There will be no two consecutive operators in the input.
-   Every number and running calculation will fit in a signed 32-bit integer.


括號展開/變號

When expanding/removing the parentheses, we only need to know the totally effective sign for this parentheses. 

We always maintain the totally effective sign when we see a new sign/operation(+ -). 
If the next coming guy is number, this is used to add/subtract that number toward the total result. 
If the next coming guy is parenthesis, this is used to flip all plus/minus inside the parentheses.

Eg for
( - ( + ( + ( - ( + ( blabla
`- + + - + ` will be a +
so totally effective sign for blabla is +

After finishing (blabla), we need to know the previous  totally effective sign ===> use a stack

```python=
class Solution:
    def calculate(self, s: str) -> int:
        # 1 for "+"; -1 for "-"
        # sign-changing operations encountered before reaching here
        operations = [1]  
        # cur_sign is math.prod(operations)
        current_sign = 1 
        result = 0
        n = len(s)
        i = 0
        while i < n:
            if s[i] == ' ':
                i += 1
            elif s[i] == '+':
                # operations[-1] is the effective sign contolling the current parenthesis level
                # so current_sign is the effective sign for the coming number or coming parenthesis
                # for initial condition, operations is [+1]
                current_sign = operations[-1] * (+1)
                i += 1
            elif s[i] == '-':
                current_sign = operations[-1] * (-1)
                i += 1
            elif s[i] == '(':
                # so this current_sign will control the coming parenthesis
                operations.append(current_sign)
                i += 1
            elif s[i] == ')':
                # we are leaving this parenthesis, need to know the previous effective sign contolling the previous parenthesis
                operations.pop()
                i += 1
            else:
                # get this number
                current_number = 0
                while i < n and s[i].isdigit():
                    current_number = current_number * 10 + int(s[i])
                    i += 1
                
                # current_sign is already maintained when we previously encounterd +-
                # for initial condition, current_sign is +
                result += current_number * current_sign
        return result
        
        
```

![](https://hackmd.io/_uploads/HkwcoI4Tq.png)


<!-- 復雜度分析

    時間復雜度：O(n)O(n)O(n)，其中 nnn 為字符串 sss 的長度。需要遍歷字符串 sss 一次，計算表達式的值。

    空間復雜度：O(n)O(n)O(n)，其中 nnn 為字符串 sss 的長度。空間復雜度主要取決於棧的空間，棧中的元素數量不超過 nnn。
 -->


![](https://hackmd.io/_uploads/Sk5OsIE6c.png)


<!-- 方法一：括號展開 + 棧

由於字符串除了數字與括號外，只有加號和減號兩種運算符。因此，如果展開表達式中所有的括號，則得到的新表達式中，數字本身不會發生變化，只是每個數字前面的符號會發生變化。

因此，我們考慮使用一個取值為 {−1,+1}\{-1,+1\}{−1,+1} 的整數 sign\textit{sign}sign 代表「當前」的符號。根據括號表達式的性質，它的取值：

    與字符串中當前位置的運算符有關；
    如果當前位置處於一系列括號之內，則也與這些括號前面的運算符有關：每當遇到一個以 −-− 號開頭的括號，則意味著此後的符號都要被「翻轉」。

考慮到第二點，我們需要維護一個棧 ops\textit{ops}ops，其中棧頂元素記錄了當前位置所處的每個括號所「共同形成」的符號。例如，對於字符串 1+2+(3-(4+5))\text{1+2+(3-(4+5))}1+2+(3-(4+5))：

    掃描到 1+2\text{1+2}1+2 時，由於當前位置沒有被任何括號所包含，則棧頂元素為初始值 +1+1+1；
    掃描到 1+2+(3\text{1+2+(3}1+2+(3 時，當前位置被一個括號所包含，該括號前面的符號為 +++ 號，因此棧頂元素依然 +1+1+1；
    掃描到 1+2+(3-(4\text{1+2+(3-(4}1+2+(3-(4 時，當前位置被兩個括號所包含，分別對應著 +++ 號和 −-− 號，由於 +++ 號和 −-− 號合並的結果為 −-− 號，因此棧頂元素變為 −1-1−1。

在得到棧 ops\textit{ops}ops 之後， sign\textit{sign}sign 的取值就能夠確定了：如果當前遇到了 +++ 號，則更新 sign←ops.top()\textit{sign} \leftarrow \text{ops.top()}sign←ops.top()；如果遇到了遇到了 −-− 號，則更新 sign←−ops.top()\textit{sign} \leftarrow -\text{ops.top()}sign←−ops.top()。

然後，每當遇到 ((( 時，都要將當前的 sign\textit{sign}sign 取值壓入棧中；每當遇到 ))) 時，都從棧中彈出一個元素。這樣，我們能夠在掃描字符串的時候，即時地更新 ops\textit{ops}ops 中的元素。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/basic-calculator/solution/ji-ben-ji-suan-qi-by-leetcode-solution-jvir/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 -->