856-score-of-parentheses.md

856. Score of Parentheses - 括号的分数

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

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

 

示例 1：

输入： "()"
输出： 1

示例 2：

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

示例 3：

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

示例 4：

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

 

提示：

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

---

题目标签：Stack / String

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
python3	68 ms	N/A

class Solution:
    def scoreOfParentheses(self, S):
        """
        :type S: str
        :rtype: int
        """
        s = []
        for c in S:
            if c == '(':
                s.append(c)
            else:
                if s[-1] == '(':
                    s[-1] = 1
                else:
                    if '(' in s:
                        n = 0
                        for i in range(len(s)-1, -1, -1):
                            if s[i] == '(':
                                s.pop()
                                break
                            else:
                                n += s.pop()
                        s.append(n * 2)
        return sum(s)