856. 括号的分数

解法一：递归

先按照规则2划分成多个子串，符合规则1的就为1，符合规则3就解开一层括号，进一步递归求解。

class Solution {
    public int scoreOfParentheses(String S) {
        return sum(S, 0, S.length() - 1);
    }
    private int sum(String S, int left, int right) {
        int begin = left;
        int ans = 0;
        int count = 0;
        for (int i = left; i <= right; ++i) {
            if (S.charAt(i) == '(') {
                ++count;
            } else {
                --count;
            }
            // 规则2
            if (count == 0) {
                // 规则1
                if (i == begin + 1) {
                    ++ans;
                } else { // 规则3
                    ans += sum(S, begin + 1, i - 1) * 2;
                }
                begin = i + 1;
            }
        }
        return ans;
    }
}

解法二：栈

官方题解：https://leetcode-cn.com/problems/score-of-parentheses/solution/gua-hao-de-fen-shu-by-leetcode/
遇到(就入栈，遇到)就出栈，分规则1和规则3两种情况计算数值。

class Solution {
    public int scoreOfParentheses(String S) {
        Deque<Integer> stack = new LinkedList<>();
        int u, v;
        // 栈底存储最终答案
        stack.push(0);
        for (char ch : S.toCharArray()) {
            if (ch == '(') {
                stack.push(0);
            } else {
                u = stack.pop();
                v = stack.pop() + Math.max(u * 2, 1);
                stack.push(v);
            }
        }
        return stack.pop();
    }
}

解法三：统计()的个数

根据当前括号嵌套深度计算该()展开后的数值。参考官方题解。

class Solution {
    public int scoreOfParentheses(String S) {
        int ans = 0;
        // 括号嵌套深度
        int depth = 0;
        for (int i = 0; i < S.length(); ++i) {
            if (S.charAt(i) == '(') {
                ++depth;
            } else {
                --depth;
                if (S.charAt(i - 1) == '(') {
                    ans += 1 << depth;
                }
            }
        }
        return ans;
    }
}