# Leetcode 224. Basic Calculator

## 題解

### 使用棧紀錄 ( 位置回朔

class Solution:
    def calculate(self, s: str) -> int:
        n = len(s)
        stack = []
        s_left = []
        op = "+"
        fop = {"+","-"}
        num = 0
        for i in range(n):
            cs = s[i]
            if not cs.isdigit() and num > 0:
                stack.append(num * -1 if op == "-" else num)
                num = 0
                op = "+"
            if cs.isdigit():
                num = num * 10 + int(cs)
                if i == n-1:
                    stack.append(num * -1 if op == "-" else num)
            elif cs == "(":
                s_left.append((len(stack),op))
                op = "+"
            elif cs == ")":
                stack_n, op = s_left.pop()
                _num = 0
                while len(stack) > stack_n:
                    _num += int(stack.pop())
                if op == '-':
                    _num = _num * -1
                stack.append(_num)
                op = "+"
            elif cs in fop:
                op = cs
        return sum(stack)

### 官解

反轉 sign 位決定數字是否為負數

class Solution:
    def calculate(self, s: str) -> int:
        n = len(s)
        i = 0
        output = 0
        sign = 1
        ops = [1] # 紀錄有多少 ( 以及當下的狀態是正數還是負數
        while i < n:
            if s[i] == " ":
                i += 1
            elif s[i] == "+": # 紀錄當下狀態為正數
                sign = ops[-1]
                i += 1
            elif s[i] == "-": # 紀錄當下狀態為負數
                sign = -ops[-1]
                i += 1
            elif s[i] == "(": # 紀錄 ( 位置時的 sign 狀態
                ops.append(sign)
                i += 1
            elif s[i] == ")": # 到達 ) 代表上一個狀態 ops[-1] 已經沒有用了
                ops.pop()
                i += 1
            else:
                num = 0
                while i < n and s[i].isdigit():
                    num = num * 10 + int(s[i])
                    i += 1
                output += num * sign # 這裡決定正數還是負數
        return output