Leetcode 856. Score of Parentheses 括号得分(栈)
Leetcode 856. Score of Parentheses 括号得分(栈)
racaljk
发布于 2018-12-12 10:03:05
发布于 2018-12-12 10:03:05
Leetcode 856. Score of Parentheses 括号得分(栈)
题目描述
字符串S包含平衡的括号（即左右必定匹配），使用下面的规则计算得分
()得1分AB得A+B的分，比如()()得2分(A)得2A分， 比如(()())得2(1+1)分
测试样例
Example 1:
Input: "()"
Output: 1
Example 2:
Input: "(())"
Output: 2
Example 3:
Input: "()()"
Output: 2
Example 4:
Input: "(()(()))"
Output: 6详细分析
简而言之，遇到右括号就一直出栈并累加到一个值直到遇到左括号，这个累加值就表示这对括号的得分。如此周而复始到字符串结尾即可。
具体言之，遇到 ( 就入栈，这里入一个毒药值-1，然后遇到 ) 就一直出栈，累加到score，直到遇到毒药值-1，最后把累加的score入栈，表示这对括号的最终得分。
最后计算栈中的结果之和即可。至于为什么是栈结果和而不是栈顶一个值是因为输入可能是()()，这种，最后栈中是| 1 | 1 |。
算法实现
class Solution {
public:
int scoreOfParentheses(string S) {
stack<int> s;
int i=0;
while(S[i]!=0){
if(S[i]=='('){
s.push(-1);
}else if(S[i]==')'){
int score = 0;
if(s.top()==-1){
s.pop();
s.push(1);
}else{
while(!s.empty()){
int t = s.top();
if(t==-1){
s.pop();
s.push(score);
break;
}
score+= t*2;
s.pop();
}
}
}
i++;
}
int result = 0;
while(!s.empty()){
result += s.top();
s.pop();
}
return result;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-11-11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录