856. 括号的分数

Difficulty
Medium
Tags
栈
URL
https://leetcode.cn/problems/score-of-parentheses/
Star
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
  • () 得 1 分。
  • AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
  • (A) 得 2 * A 分，其中 A 是平衡括号字符串。
示例 1：
输入："()"
输出：1
示例 2：
输入："(())"
输出：2
示例 3：
输入："()()"
输出：2
示例 4：
输入："(()(()))"
输出：6
提示：
  1. S 是平衡括号字符串，且只含有 ( 和 ) 。
  1. 2 <= S.length <= 50
通过次数20,405提交次数32,258

法1 栈模拟

思路
直接用栈模拟即可：
左括号入栈
右括号，则从栈中不断弹出，直到遇到左括号，且将弹出的元素累加。
题解
class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = []
        for i in range(0, len(s)):
            if s[i] == "(":
                stack.append("(")
            else:
                temp = 0
                while len(stack) > 0 and stack[-1] != "(":
                    temp += stack.pop()
                stack.pop()
                stack.append( max(1, 2 * temp))

        res = 0
        while stack:
            res += stack.pop()

        return res