难度：★★★☆☆
类型：字符串
方法：栈

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

j题目

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

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

示例 1：

输入： "()"
输出： 1

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

解答

括号的问题可以用栈解决。题目中已经说明括号字符串是合法的，我们无需考虑别的。

括号存在包含关系时内部分数乘以2，存在并列关系时分数相加。

我们准备一个栈，栈里存储的是括号分数，从左到右遍历括号，每当遇到一个左括号，则把数字0压入栈中，每当遇到一个右括号，弹出栈顶元素，做以下处理：

1. 如果被弹出的栈顶元素是零，说明这个零是刚刚被压入栈中的，当前的右括号直接与其对应的左括号相邻，当前元素的分数记录为1；

2. 如果被弹出栈顶的元素不是零，说明当前右括号与其对应的左括号隔着一些括号，这时弹出的栈顶元素需要乘以2。

将计算得到的数字与栈顶元素相加，因为存在并列关系。

class Solution(object):
    def scoreOfParentheses(self, S):
        stack = [0]

        for x in S:
            if x == '(':
                stack.append(0)
            else:
                v = stack.pop()
                stack[-1] += 1 if v == 0 else 2 * v

        return stack.pop()

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析