Lintcode 1491. 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

Example 1:

Input: "()"
Output: 1

Example 2:

Input: "(())"
Output: 2

Notice

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

Code (Java):

public class Solution {
    /**
     * @param S: a string
     * @return: the score of the string
     */
    public int scoreOfParentheses(String S) {
        // Write your code here
        if (S == null || S.length() == 0) {
            return 0;
        }
        
        // stores the index of the left parathesis
        Stack<Integer> paraStack = new Stack<>();
        
        // store the pair of (res, left boundary), res is the current 
        // result, left boundary is the left starting index of the result
        Stack<int[]> numStack = new Stack<>(); 
        
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            
            if (c == '(') {
                paraStack.push(i);
            } else {
                int leftIdx = paraStack.pop();
                
                // case 1: it's only ()
                if (i - leftIdx == 1) {
                    numStack.push(new int[]{1, leftIdx});
                } else {
                    // case 2: (())
                    int curAns = 0;
                    while (!numStack.isEmpty() && numStack.peek()[1] > leftIdx) {
                        curAns += numStack.pop()[0];
                    }
                    
                    curAns *= 2;
                    
                    numStack.push(new int[]{curAns, leftIdx});
                }
            }
        }
        
        int ans = 0;
        while (!numStack.isEmpty()) {
            ans += numStack.pop()[0];
        }
        
        return ans;
    }
}