# 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

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
        
        


<!-- 復雜度分析

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

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


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

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

因此，我們考慮使用一個取值為 {−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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 -->