Score of Parentheses

Given a balanced parentheses string S, 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) {
        S = '(' + S + ')';
        Deque<String> st = new LinkedList<>();
        for (char c : S.toCharArray()) {
            if (c == ')') {
                int sum = 0;
                while (!st.peek().equals("("))
                    sum += Integer.parseInt(st.pop());
                st.pop();
                st.push(sum == 0 ? "1" : Integer.toString(sum * 2));
            } else
                st.push(c + "");
        }
        return Integer.parseInt(st.pop()) / 2;
    }
}