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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

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;     } }