题目描述

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

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

输入输出样例

Input: "()"
Output: 1

Input: "(())"
Output: 2

Input: "()()"
Output: 2

Input: "(()(()))"
Output: 6

解题思路

这题很明显，就是去找平衡括号()。但是这个找添加了一个额外的附加条件，即包含在内的平衡括号会应用规则 2 * A。那么麻烦就来了，如何找到这些个平衡括号，且在内的会双倍计数呢?
从平衡括号下手，既然是去找平衡括号，那么一个左括号就会有一个右括号与之对应。即对左括号进行计数，那么找平衡括号的问题解决了，那么在平衡括号内的计数翻倍又应如何实现呢?
这个问题就是解决样例二与样例三的计数问题，为了解决这个计数问题，需要将原先的左括号计数改为位置操作。当遇到左括号则存储，遇到右括号则进行计算操作。即一层层的向外计算，举例"(())"。

首先数组中存入了两个左括号
遇到第一个右括号后，弹出最后存入的左括号，计平衡括号个数为1，存入数组
再遇到右括号后，弹出左括号，判断先前是否有平衡括号，有则双倍，因此将结果2存入数组

按照这个思路，具体的实现代码如下所示:

class Solution {
public:
    int scoreOfParentheses(string s) {
        vector<int> ans;
        for (auto x : s) {
            if (x == '(') {
                ans.push_back(-1); // 左括号标志
            } else {
                int re = 0;
                while (ans.back() != -1) {
                    // 计数已有的平衡括号
                    re += ans.back();
                    ans.pop_back();
                }
                ans.pop_back();
                ans.push_back((re == 0) ? 1 : re * 2);
            }
        }
        // 计算数组总和解决场景 "()()"
        return accumulate(ans.begin(), ans.end(), 0);
    }
}

Rabbet

括号的分数

题目描述

输入输出样例

解题思路