【栈】括号的分数

题目

856. 括号的分数

---

给定一个平衡括号字符串 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

解题

方法一：栈模拟

思路

维护一个栈(stk)记录分数，首先把 0 压入栈表示没有括号的时候得到的是 $0$ 分，然后开始正序遍历字符串：

• 如果遇到了 '(' ，向栈中压入一个 $0$ 占位，因为该括号还未封闭。
• 如果遇到了 ')' ，弹出栈顶元素(score)：
  • 如果此时 score 为 $0$ 说明该括号中间没有嵌套，那么根据规则一该括号可以贡献的分数就是 $1$。
  • 如果此时 score 不为 $0$ 说明该括号中间有嵌套，那么根据规则三该括号可以贡献的分数就要翻倍为 score * 2。
  • 然后再加上前一个括号的分数（规则二）就得到了字符串遍历到这里时的总分数。

最后返回栈顶元素就是 s 的分数。

代码

class Solution {
    public int scoreOfParentheses(String s) {
        Deque<Integer> stk = new LinkedList<>();
        stk.push(0);
        for (char ch : s.toCharArray()) {
            if (ch == '(') stk.push(0);
            else {
                int score = stk.pop();
                stk.push(stk.pop() + (score == 0 ? 1 : score * 2));
            }
        }
        return stk.pop();
    }
}