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;

    }

};

巴特西

Leetcode 856. Score of Parentheses 括号得分(栈)

Leetcode 856. Score of Parentheses 括号得分(栈)

题目描述

测试样例

详细分析

算法实现

最新文章

热门文章