856. Score of Parentheses

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        st = [] 
        for c in s:
            if c == '(':
                st.append(c)
            else: # c == )
                if st[-1] == '(':
                    st.pop()
                    st.append('1')
                elif st[-1].isdigit():
                    x = int(st.pop())
                    while st[-1].isdigit():
                        x += int(st.pop()) # AB => A + B 
                    x = x *2 
                    st.pop()
                    st.append(str(x))
        return sum([int(x) for x in st]) # convert string number into int type 
####################################to keep same type in stack all the time ###################

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        """tc O(N)  sc O(N)
        main idea: 
        if we meet (, we push cur into stack and enter next inner leyer ;
        and reset cur 
        
        each time we meet ), cur score will be doubled and will be at least 1 
        we exit current layer and set cur += st.pop() + cur 
        
        """
        
        st = [] 
        cur = 0
        for c in s:
            if c == '(':
                st.append(cur)
                cur = 0
            else: # c == )
                cur = st.pop() + max(2*cur,1) 
        return cur 

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        """tc O(N)  sc O(1)
        main idea: keep counting number of layers current score is at  
        for each ( , layer + 1
        for each ) , layer - 1
        when we encounter a () consequtively, we get to know its outer number of layers L => new_score = 2^ L 
        """
        l = res = 0
        for i,c in enumerate(s):
            if c == '(':
                l += 1
            else:
                l -= 1
            if c == ')' and s[i-1]== '(':
                res += 1 << l #2**l
        return res