Score of Parentheses

Problem Statement

In the given problem, you are provided with a string s that comprises only balanced parentheses. The objective is to compute the score of this string based on specific scoring rules for combinations of parentheses:

• A single pair "()" directly translates to a score of 1.
• The concatenation of two balanced strings A and B is scored as the sum of their individual scores, denoted as A + B.
• A balanced string enclosed within another pair of parentheses, represented as (A), has its score doubled, thus the score is 2 * A.

Your task is to implement a function that, given such a balanced parentheses string, returns its calculated score per the rules outlined.

Examples

Example 1

Input:

s = "()"

Output:

1

Example 2

Input:

s = "(())"

Output:

2

Example 3

Input:

s = "()()"

Output:

2

Constraints

• 2 <= s.length <= 50
• s consists of only '(' and ')'.
• s is a balanced parentheses string.

Approach and Intuition

To derive a solution, consider the structured nature of the balanced parentheses and how each configuration contributes to the overall score.

1. Initialize a counter to track the depth of nested parentheses which is helpful to understand how to apply the doubling rule (A).
2. Traverse the string s from left to right to evaluate and calculate the score:
   • Upon encountering an opening bracket (, you can increase the depth.
   • Upon finding a closing bracket ), check:
     • If it closes a direct simple pair (), score this as 1. If these are nested further inside other parentheses, the context (or depth) matters, meaning you multiply this score based on its depth.
     • Decrease the depth after scoring a closed pair, as it denotes the end of a nesting level.
3. For consecutive balanced substrings like ()(), sum their scores directly as they are not nested but simply adjacent.
4. Use a stack to effectively manage and keep track of scores in relation to their depth.
5. By following the depth and stack mechanism, every score piece either gets directly added or multiplied and accumulated into the final score.

Application using Examples

• In the first example (s = "()"), the string is directly a simple pair, so the score is straightforwardly 1.
• In the second example (s = "(())"), the inner () constitutes a simple score of 1, but its embedding within another pair doubles this score to 2.
• In the third example (s = "()()"), we see two simple pairs next to each other, neither of which is nested inside another, so we sum their scores: 1+1=2.

This method uses the inherent properties of balanced parentheses where deeper nesting affects the multiplication of scores, while juxtaposition leads to a summation of scores. Thus, managing the depth and order of operations correctly is key to implementing this solution efficiently.

Solutions

class Solution {
    
    public int calculateScore(String input) {
        int totalScore = 0, depth = 0;
        for (int index = 0; index < input.length(); ++index) {
            if (input.charAt(index) == '(') {
                depth++;
            } else {
                depth--;
                if (input.charAt(index - 1) == '(')
                    totalScore += 1 << depth;
            }
        }
    
        return totalScore;
    }
}