October 5Medium

Score of parentheses

String
Stack
Bracket Sequences

Problem

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rule: 1. "()" has score 1. 2. AB has score A + B, where A and B are balanced parentheses strings. 3. (A) has score 2 * A, where A is a balanced parentheses string.

Solution

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = []

        for i in range(len(s)):
            if s[i] == "(":
                stack.append("(")
            else:
                total = 0
                while stack[-1] != "(":
                    total += stack.pop()
                stack[-1] = 2*total if total else 1
        return sum(stack)