题目描述

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

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

样例

输入："()"
输出：1

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

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

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

注意

• S 是平衡括号字符串，且只含有 ( 和 )。
• 2 <= S.length <= 50

算法

(栈) $O(n)$

1. 定义一个记录分数的栈，初始时放入 0 当做答案。
2. 如果遇到左括号，则 0 入栈。
3. 如果遇到右括号，则弹出栈顶；如果栈顶元素为 t = 0，则说明右括号是和上一个左括号相邻的，故此时的栈顶加 1；否则此时的栈顶加 2 * t。
4. 最后栈中一定还剩一个元素，这个元素就是答案。

时间复杂度

• 仅需要遍历所以字符一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的栈空间，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int scoreOfParentheses(string S) {
        stack<int> score;
        score.push(0);
        for (auto &c : S) {
            if (c == '(')
                score.push(0);
            else {
                int t = score.top();
                score.pop();
                if (t == 0)
                    score.top() += 1;
                else
                    score.top() += 2 * t;
            }
        }
        return score.top();
    }
};