Leetcode每日一题 —— 856. 括号的分数

力扣 LeetCode

856. 括号的分数 - 力扣（LeetCode）

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

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

示例 1：

输入： "()"
输出： 1

示例 2：

输入： "(())"
输出： 2

示例 3：

输入： "()()"
输出： 2

示例 4：

输入： "(()(()))"
输出： 6

提示：

1....

思路

栈应用题，表达式解析。

实际上我们只用在栈中维护得分以及标记出现的左括号，这里咱用 -1 来标记了左括号。遇到右括号时就可以开始弹栈，直至遇到左括号 (-1) 为止的分数都可以相加起来得到 sum，这个 sum 就是当前这一对括号的内层分数，需要计算 \mathrm{sum} \times 2。但注意内层可能没有括号，所以取的是 \max(\mathrm{sum} \times 2,\ 0)。

最后位于最外层，把栈中剩余的分数累加即可。

代码```
class Solution {
public:
int scoreOfParentheses(string s) {
// 保证 s 是闭合的括号
// 维护一个存储得分的栈
stack<int> stk;
for(int i=0;i<s.size();i++){
if(s[i]=='('){
// 栈中用 -1 标记左括号
stk.emplace(-1);
}else if(s[i]==')'){
// 遇到右括号，弹栈直至遇到左括号
// 注意这里要判断嵌套
int innerScore=0; // 累加计算内层分数
while(stk.top()!=-1){
innerScore+=stk.top();
stk.pop();
}
// 可能当前括号是 '()', 没有内层，算 1
// 如果有内层就要 x2
innerScore=max(innerScore*2,1);
stk.pop();
stk.emplace(innerScore);
}
}
int res=0;
// 最后把最外层的括号累加起来
while(!stk.empty()){
res+=stk.top();
stk.pop();
}
return res;
}
};