# 856. Score of Parentheses

###### tags: `leetcode`,`medium`

>ref: https://leetcode.com/problems/score-of-parentheses/
>
Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rule:

"()" has score 1.
AB has score A + B, where A and B are balanced parentheses strings.
(A) has score 2 * A, where A is a balanced parentheses string.

>Example 1:
Input: s = "()"
Output: 1

>Example 2:
Input: s = "()()"
Output: 2

>Constraints:
2 <= s.length <= 50
s consists of only '(' and ')'.
s is a balanced parentheses string.

>1. when an pair exist, count that pair's value
>2. check the pair by watch s.charAt(i-1)=="(" or the pair is not count as value
>3. timeCom(O(n)): loop once , spatialCom(O(1))

    public int scoreOfParentheses(String s) {

        int dep=0;
        
        int count =0;
        
        for(int i=0; i< s.length();i++){
            
            if(s.charAt(i)=='('){
                dep++;
            }else{
                dep--;
                if(s.charAt(i-1)=='('){
                     count+= (1 << dep);
                }
            }
        }
        
        return count;
        
        
    }

init dumb resolve : stack

>1. create stack record
>2. check the pair and replace pair as value, add the number until meet the "("
>3. in the final, pile up the stack value as answer
>3. timeCom(O(n)): loop once , spatialCom(O(N)): stack

    public int scoreOfParentheses(String s) {
        
        String[] s1=s.split("");
        
        Stack<Integer> re= new Stack<>();
        
        int count=0;
        
        for(String ss:s1){
            if(ss.equals("(")){
                re.add(-1);
            }else{
                Integer load=0;
                
                while(re.peek()!=-1){
                    load+=re.pop();
                }
                re.pop();
                if(load==0){
                    load=1;
                }else{
                    load*=2;
                }
                re.add(load);
            }  
        }
        
        int res=0;
        while(re.size()!=0){
            res+=re.pop();
        }
        
         
        return res;
        
    }