# **Leetcode筆記(Score of Parentheses)**

:::info
:information_source: 題目 : Score of Parentheses, 類型 : stack , 等級 : medium
日期 : 2023/12/01
:::

### 嘗試

---
### **優化**
用stack去存，處理base case跟要累加(*2)的，還沒有清空則繼續累加直到清空

"""
output
((()))()
stack = [0]
if n == 0:
    val = 1
else:
    val = n * 2
stack not empty -> stack[-1] + val
stack is empty -> output + val
output = 4 + 1 = 5
"""

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = []
        output = 0
        for c in s:
            if c == "(":
                stack.append(0)
            elif c == ")":
                # check the number in stack
                n = stack.pop()
                if n == 0: # base case
                    val = 1
                else:
                    val = n * 2
                # if they are all pair
                if not stack:
                    output += val
                else: # keep doing (they are not pair)
                    # ((())()) 
                    # ( 2  1)
                    stack[-1] += val

        return output

去累加現階段的(((，每次遇到第一個)就去處理前面所有的(

"""
((())())()
accu = 3 (((
accu = 2 )
output = 4
accu = 1 )
accu = 2 (
accu = 1 )
output = 4 + 2 = 6
accu = 0 )
accu = 1 (
accu = 0 )
output = 6 + 1 = 7
"""

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        output = 0
        accu = 0
        for i, p in enumerate(s):
            if p == "(":
                accu += 1
            elif p == ")":
                accu -= 1
                if s[i - 1] == "(":
                    output += 2 ** accu
        
        return output

---

**思路**

**講解連結**
https://www.youtube.com/watch?v=XDM7H3t_V54
Provided by. Timothy H Chang