Given a balanced parentheses stringS, compute the score of the string 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: 
"()"
Output: 
1

Example 2:

Input: 
"(())"
Output: 
2

Example 3:

Input: 
"()()"
Output: 
2

Example 4:

Input: 
"(()(()))"
Output: 
6

Note:

1. S is a balanced parentheses string, containing only ( and ) .
2. 2 < = S.length < = 50

class Solution {
    public int scoreOfParentheses(String S) {
        Stack<String> stack = new Stack<>();
        for (char c : S.toCharArray()){
            if (c == '(') stack.push(c + "");
            else{
                if (stack.peek().equals("(")){
                    stack.pop();
                    stack.push("1");
                }
                else{
                    int sum = 0;
                    while (!stack.peek().equals("(") && !stack.peek().equals(")")){
                        sum += Integer.parseInt(stack.pop());
                    }
                    stack.pop();
                    stack.push(sum * 2 + "");
                }
            }
        }

        int ans = 0;
        while (!stack.isEmpty()){
            ans += Integer.parseInt(stack.pop());
        }

        return ans;
    }
}