给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

  • () 得 1 分。
  • AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
  • (A) 得 2 * A 分，其中 A 是平衡括号字符串。

示例 1：

输入： “()”
输出： 1

示例 2：

输入： “(())”
输出： 2

示例 3：

输入： “()()”
输出： 2

示例 4：

输入： “(()(()))”
输出： 6

提示：

  1. S 是平衡括号字符串，且只含有 ( 和 ) 。
  2. 2 <= S.length <= 50
    https://leetcode-cn.com/problems/score-of-parentheses/

    方法一：分治

    对于一个字符串 S，我们将左括号 ( 记为 1，右括号记为 -1，如果 S 的某一个非空前缀对应的和为 0，那么这个前缀就是一个平衡括号字符串。我们遍历字符串 S，得到若干个前缀和为 0 的位置，就可以将字符串拆分为 S = P_1 + P_2 + … + P_n，其中每一个 P_i 都是一个平衡括号字符串。这样我们就可以分别计算每一个 P_i 的分数再相加，即 score(S) = score(P_1) + score(P_2) + … + score(P_n)。

对于一个不可拆分的平衡括号字符串，如果它为 ()，那么就得 1 分，否则它的最外层一定有一对左右括号，可以将这对括号去除后继续进行拆分，再将得到的分数乘 2。

  1. class Solution {
  3.     public int scoreOfParentheses(String S) {
  4.         return F(S, 0, S.length());
  5.     }
  7.     public int F(String S, int i, int j) {
  8.         //Score of balanced string S[i:j]
  9.         int ans = 0, bal = 0;
  11.         // Split string into primitives
  12.         for (int k = i; k < j; ++k) {
  13.             bal += S.charAt(k) == '(' ? 1 : -1;
  14.             if (bal == 0) {
  15.                 if (k - i == 1) ans++;//如果()紧挨着
  16.                 else ans += 2 * F(S, i+1, k);//如果没有紧挨着,证明里面还有()
  17.                 i = k+1;//记录左括号的位置
  18.             }
  19.         }
  20.         return ans;
  21.     }
  22. }

方法二：栈

字符串 S 中的每一个位置都有一个“深度”，即该位置外侧嵌套的括号数目。例如，字符串 (()(.())) 中的 . 的深度为 2，因为它外侧嵌套了 2 层括号：((.))。
我们用一个栈来维护当前所在的深度，以及每一层深度的得分。当我们遇到一个左括号 ( 时，我们将深度加一，并且新的深度的得分置为 0。当我们遇到一个右括号 ) 时，我们将当前深度的得分乘二并加到上一层的深度。这里有一种例外情况，如果遇到的是 ()，那么只将得分加一。

下面给出了字符串 (()(())) 每次对应的栈的情况：

  • [0, 0] (
  • [0, 0, 0] ((
  • [0, 1] (()
  • [0, 1, 0] (()(
  • [0, 1, 0, 0] (()((
  • [0, 1, 1] (()(()
  • [0, 3] (()(())

  • [6] (()(())) ```java public int scoreOfParentheses(String S) { Stack stack = new Stack(); stack.push(0); // The score of the current frame

    for (char c: S.toCharArray()) {

    1.   if (c == '(')
    2.       stack.push(0);
    3.   else {
    4.       int v = stack.pop();
    5.       int w = stack.pop();
    6.       stack.push(w + Math.max(2 * v, 1));
    7.   }

    }

    return stack.pop(); }

<a name="uV2g7"></a>
#### 方法三：统计核心的数目
事实上，我们可以发现，只有 () 会对字符串 S 贡献实质的分数，其它的括号只会将分数乘二或者将分数累加。因此，我们可以找到每一个 () 对应的深度 x，那么答案就是 2^x 的累加和。

```java
class Solution {

    public int scoreOfParentheses(String S) {
        int ans = 0, bal = 0;
        for (int i = 0; i < S.length(); ++i) {
            if (S.charAt(i) == '(') {
                bal++;
            } else {
                bal--;
                if (S.charAt(i-1) == '(')
                    ans += 1 << bal;
            }
        }

        return ans;
    }
}