Score Of Parentheses - Leetcode Solution

Problem Statement:

Given a balanced parentheses string S, compute the score of the string based on the following rule:

• () has score 1
• AB has score A + B, where A and B are balanced parentheses strings.
• (A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: "()" Output: 1

Example 2:

Input: "(())" Output: 2

Example 3:

Input: "()()" Output: 2

Example 4:

Input: "(()(()))" Output: 6

Solution:

The solution to this problem involves using a stack data structure. We iterate through the input string one character at a time. If the current character is an opening parenthesis, we push it onto the stack. If the current character is a closing parenthesis, we pop the top element from the stack to see what it matches with.

• If the matching element is "()", then we have a score of 1.
• If the matching element is "(A)", then we have a score of 2 * A, where A is the score of the balanced parentheses string inside the parentheses.
• If the matching elements are "AB", then we have a score of A + B, where A and B are the scores of the two balanced parentheses strings.

In order to keep track of the scores, we create two variables, current and total. The current variable keeps track of the score of the current balanced parentheses string we are parsing, while the total variable keeps track of the total score of the entire string.

Pseudocode:

Initialize an empty stack. Initialize current and total to 0.

Iterate through each character in the input string: If the current character is an opening parenthesis: Push it onto the stack. Update current to 0.

If the current character is a closing parenthesis:
    Pop the top element from the stack.
    If the top element is "()", then update current to 1.
    If the top element is "(A)", then update current to 2 * A, where A is the score of the balanced parentheses string inside the parentheses.
    If the top element is "AB", then update current to A + B, where A and B are the scores of the two balanced parentheses strings.
    
    If there are any elements left in the stack, add the current score to the score of the element on top of the stack.
    Otherwise, add the current score to the total score.
    

Return the total score.

Time Complexity: O(n) - where n is the length of the input string.

Python Code:

class Solution: def scoreOfParentheses(self, S: str) -> int: stack = [] current_score = 0 total_score = 0

    for char in S:
        if char == '(':
            stack.append(char)
            current_score = 0
            
        elif char == ')':
            matched_parentheses = stack.pop()
            if matched_parentheses == '(':
                current_score = 1
            else:
                current_score = 2 * current_score
                
                while len(stack) > 0 and stack[-1] != '(':
                    current_score += stack.pop()
                    
                if len(stack) > 0 and stack[-1] == '(':
                    current_score += stack.pop()
                    
            if len(stack) > 0:
                stack.append(current_score)
                
            else:
                total_score += current_score
                
    return total_score

1