『LeetCode』856 括号的分数

题目

856. 括号的分数

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

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

示例 1：

输入： "()"
输出： 1

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

标签

栈, 字符串

---

题解

【括号的分数】简单栈模拟&数学

栈模拟

关于括号的问题多半要用到栈，这题也不例外，有题意得：

• 如果是嵌套括号，得分要乘二
• 如果是并列，得分相加

所以关键是判断出栈的右括号是嵌套还是并列，其实很简单，只需要结合前一个括号就能很容易判断

• 如果 ) 前面是 (, 即 (), 那毫无疑问是并列的
• 如果 ) 前面还是 ), 即 ...)), 那自然是嵌套的

然后我们将每层的分数叠加到栈顶，最后得分就是题目所求

# Code language: Python
class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        st = [0]
        pre = ')'
        for c in s:
            if c == '(':
                st.append(0)
            else:
                cur = st.pop()
                if pre == '(':
                    cur += 1
                else:
                    cur *= 2
                st[-1] += cur
            pre = c
        return st[0]

// Code language: Java
class Solution {
    public int scoreOfParentheses(String s) {
        int ans = 0, pre = ')';
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0, n = s.length(); i < n; ++i) {
            char c = s.charAt(i);
            if (c == '(') st.addLast(0);
            else {
                int cur = st.pollLast(); 
                if (pre == '(') cur++;
                else cur *= 2;
                if (st.isEmpty()) ans += cur;
                else {
                    int tmp = st.pollLast() + cur;
                    st.addLast(tmp);
                }
            }
            pre = c;
        }
        return ans;
    }
}

// Code language: C++
class Solution {
public:
    int scoreOfParentheses(string s) {
        int ans = 0, pre = ')';
        vector<int> st;
        for (char c: s) {
            if (c == '(') st.push_back(0);
            else {
                int cur = st.back(); st.pop_back();
                if (pre == '(') cur++;
                else cur *= 2;
                if (st.empty()) ans += cur;
                else {
                    st[st.size() - 1] += cur;
                }
            }
            pre = c;
        }
        return ans;
    }
};

• 时间复杂度: \(O(n)\)
• 空间复杂度: \(O(n)\)

---

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解