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

思路

栈应用题，表达式解析。

实际上我们只用在栈中维护得分以及标记出现的左括号，这里咱用 -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;

    }

};