856. 括号的分数
题目描述
输入一个平衡的括号字符串 s，只由 ( 和 ) 组成。按以下规则递归计算它的分数，返回结果。
"()" 的分数是 1。
两个平衡括号串 A、B 直接拼接成 AB 时，分数为 A 的分数加 B 的分数。
把平衡括号串 A 用一对括号包起来成为 (A) 时，分数为 A 的分数乘 2。
示例 1
输入：s = "()" 输出：1
示例 2
输入：s = "(())" 输出：2
解释：内层 () 得 1，外面再包一层翻倍得 2。
示例 3
输入：s = "()()" 输出：2
解释：两个 () 并列，1 + 1 = 2。
数据范围
s是平衡括号字符串，只含(和)。2 <= s.length <= 50
解题思路：栈记录每层得分
用栈记录每一层括号内部已累计的分数，栈底的 0 代表最外层。遇到 ( 就进入新的一层，压入 0；遇到 ) 就结束当前层：弹出内部分数 v，这对括号的得分是 max(2v, 1)（内部为空时就是 "()" 得 1 分），把它加到外一层。
为什么正确
stack[d] 是第 d 层括号内部已经闭合的子串分数之和；栈的长度 = 当前深度 + 1。
复杂度分析
时间 O(n)；空间 O(n)（最深的嵌套层数）。
易错点
"()" 的内部分数为 0，不能直接用 2 × 0，要取 max(2v, 1)。栈底要先放一个 0 作为最外层，否则闭合最后一对括号时无处累加。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def scoreOfParentheses(self, s: str) -> int:
stack = [0]
for ch in s:
if ch == '(':
stack.append(0)
else:
v = stack.pop()
stack[-1] += max(2 * v, 1)
return stack[0]class Solution {
public int scoreOfParentheses(String s) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
for (char ch : s.toCharArray()) {
if (ch == '(') {
stack.push(0);
} else {
int v = stack.pop();
stack.push(stack.pop() + Math.max(2 * v, 1));
}
}
return stack.peek();
}
}class Solution {
public:
int scoreOfParentheses(string s) {
vector<int> stack = {0};
for (char ch : s) {
if (ch == '(') {
stack.push_back(0);
} else {
int v = stack.back();
stack.pop_back();
stack.back() += max(2 * v, 1);
}
}
return stack[0];
}
};func scoreOfParentheses(s string) int {
stack := []int{0}
for i := 0; i < len(s); i++ {
if s[i] == '(' {
stack = append(stack, 0)
} else {
v := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack[len(stack)-1] += max(2*v, 1)
}
}
return stack[0]
}var scoreOfParentheses = function(s) {
const stack = [0];
for (const ch of s) {
if (ch === '(') {
stack.push(0);
} else {
const v = stack.pop();
stack[stack.length - 1] += Math.max(2 * v, 1);
}
}
return stack[0];
};function scoreOfParentheses(s: string): number {
const stack: number[] = [0];
for (const ch of s) {
if (ch === '(') {
stack.push(0);
} else {
const v = stack.pop()!;
stack[stack.length - 1] += Math.max(2 * v, 1);
}
}
return stack[0];
}其他解法
栈法逐层模拟加法和乘 2 的规则，直观可推广；深度法先做数学化简，把空间降到 O(1)。
解法 2：按深度统计核心 () 时间 O(n)，空间 O(1)
展开规则可以发现，只有相邻的 "()" 会产生分数，外面每套一层括号就乘 2。扫描时维护当前深度：遇到 ( 深度加 1，遇到 ) 深度减 1；如果这个 ) 紧跟在 ( 后面，就把 2^深度 加到答案。
只用一个计数器，空间 O(1)，代码最短。但需要先看出“分数 = 各个核心 () 的 2^深度 之和”这个结论，不如栈法直接对应题目规则。
class Solution:
def scoreOfParentheses(self, s: str) -> int:
ans = depth = 0
for i, ch in enumerate(s):
if ch == '(':
depth += 1
else:
depth -= 1
if s[i - 1] == '(':
ans += 1 << depth
return ansclass Solution {
public int scoreOfParentheses(String s) {
int ans = 0, 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;
}
}class Solution {
public:
int scoreOfParentheses(string s) {
int ans = 0, depth = 0;
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] == '(') {
depth++;
} else {
depth--;
if (s[i - 1] == '(') ans += 1 << depth;
}
}
return ans;
}
};func scoreOfParentheses(s string) int {
ans, depth := 0, 0
for i := 0; i < len(s); i++ {
if s[i] == '(' {
depth++
} else {
depth--
if s[i-1] == '(' {
ans += 1 << depth
}
}
}
return ans
}var scoreOfParentheses = function(s) {
let ans = 0, depth = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
depth++;
} else {
depth--;
if (s[i - 1] === '(') ans += 1 << depth;
}
}
return ans;
};function scoreOfParentheses(s: string): number {
let ans = 0, depth = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
depth++;
} else {
depth--;
if (s[i - 1] === '(') ans += 1 << depth;
}
}
return ans;
}