Stack Title: fractions in parentheses

subject

Title and provenance

title ： The fraction in brackets

Source ：856. The fraction in brackets

difficulty

6 level

Title Description

requirement

Given a balanced bracket string $\text{s}$, Returns the fraction of a string .

The score of the balanced bracket string is calculated according to the following rules ：

• $\text{"()"}$ have to $\text{1}$ branch .
• $\text{AB}$ have to $\text{A}+\text{B}$ branch , among $\text{A}$ and $\text{B}$ Is a balanced parenthesis string .
• $\text{(A)}$ have to $\text{2}\times \text{A}$ branch , among $\text{A}$ Is a balanced parenthesis string .

Example

Example 1：

Input ：$\text{s = "()"}$
Output ：$\text{1}$

Example 2：

Input ：$\text{s = "(())"}$
Output ：$\text{2}$

Example 3：

Input ：$\text{s = "()()"}$
Output ：$\text{2}$

Example 4：

Input ：$\text{s = "(()(()))"}$
Output ：$\text{6}$

Data range

• $\text{2}\le \text{s.length}\le \text{50}$
• $\text{s}$ Contains only $\text{‘(’}$ and $\text{‘)’}$
• $\text{s}$ Is a balanced parenthesis string

Solution 1

Ideas and algorithms

Due to the given string $s$ Is a balanced parenthesis string , So every left parenthesis has a right parenthesis matching . According to the rules of score calculation , Scores are related to nesting levels and primitive scores . The meaning of the primitive is a non empty balanced string , It cannot be split into two balanced string splicing forms .

To calculate the fraction in parentheses , You can use the stack to store scores , Each time a closing bracket is encountered, the score is calculated according to the elements in the stack .

Traversing the string from left to right $s$, If you encounter an open parenthesis, you will $0$ Push , When the right bracket is encountered , There may be two situations ：

1. The first character is an open parenthesis , At this point, the current closing bracket is $\text{“()"}$ Part of , The score is $1$;

2. The previous character is a closing bracket , Then the previous right bracket has calculated the score and is put on the stack , At this time, the previous bracket is in the inner layer , The current closing parenthesis is in the outer layer , The effect of the outer bracket on the score is to multiply the sum of the scores of the inner bracket by $2$.

In both cases, the following method can be used to calculate the score at the current right bracket ： Take the elements in the stack out of the stack in turn , Until the element $0$, Elements $0$ Is the left bracket that matches the current right bracket （ Because the inner left parenthesis already matches the right parenthesis , So the inner left bracket corresponds to $0$ All have been released ）, Calculate the sum of stack elements $\text{score}$, Then calculate the score at the current closing bracket . according to $\text{score}$ Value , The calculation methods are as follows ：

• If $\text{score}=0$, Then it corresponds to the above situation 1, Therefore, the current score in the right bracket is $1$;

• If $\text{score}>0$, Then it corresponds to the above situation 2, Therefore, the current score in the right bracket is $\text{score}\times 2$.

After calculating the score at the current closing bracket , Put the score on the stack .

After the traversal , The elements in the stack are strings $s$ The fraction of each primitive in , Calculate the sum of the elements in the stack , String $s$ The scores of .

Consider the following parenthesized string ：$s=\text{“()(()(()))"}$. The length of the string is $10$, The process of calculating the score is as follows .

Subscript $0$： The character is $\text{‘(’}$, take $0$ Push , Now the stack is $[0]$, The left side is the bottom of the stack , On the right is the top of the stack .

Subscript $1$： The character is $\text{‘)’}$, take $0$ Out of the stack , take $1$ Push , Now the stack is $[1]$.

Subscript $2$： The character is $\text{‘(’}$, take $0$ Push , Now the stack is $[1,0]$.

Subscript $3$： The character is $\text{‘(’}$, take $0$ Push , Now the stack is $[1,0,0]$.

Subscript $4$： The character is $\text{‘)’}$, take $0$ Out of the stack , take $1$ Push , Now the stack is $[1,0,1]$.

Subscript $5$： The character is $\text{‘(’}$, take $0$ Push , Now the stack is $[1,0,1,0]$.

Subscript $6$： The character is $\text{‘(’}$, take $0$ Push , Now the stack is $[1,0,1,0,0]$.

Subscript $7$： The character is $\text{‘)’}$, take $0$ Out of the stack , take $1$ Push , Now the stack is $[1,0,1,0,1]$.

Subscript $8$： The character is $\text{‘)’}$, take $1$ Out of the stack , And then $0$ Out of the stack , take $2$ Push （$2=1\times 2$）, Now the stack is $[1,0,1,2]$.

Subscript $9$： The character is $\text{‘)’}$, take $2$、$1$ Out of the stack , And then $0$ Out of the stack , take $6$ Push （$6=(2+1)\times 2$）, Now the stack is $[1,6]$.

End of traversal , The sum of the elements in the stack is $7$, For the string $s$ The scores of .

Code

class Solution {
    
    public int scoreOfParentheses(String s) {
    
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int length = s.length();
        for (int i = 0; i < length; i++) {
    
            if (s.charAt(i) == '(') {
    
                stack.push(0);
            } else {
    
                int score = 0;
                while (stack.peek() != 0) {
    
                    score += stack.pop();
                }
                stack.pop();
                int newScore = score == 0 ? 1 : score * 2;
                stack.push(newScore);
            }
        }
        int totalScore = 0;
        while (!stack.isEmpty()) {
    
            totalScore += stack.pop();
        }
        return totalScore;
    }
}

Complexity analysis

• Time complexity ：$O(n)$, among $n$ Is string $s$ The length of . Need to traverse the string $s$ once , The scores corresponding to each subscript are put on and out of the stack once respectively .

• Spatial complexity ：$O(n)$, among $n$ Is string $s$ The length of . The space complexity mainly depends on the stack space .

Solution 2

Ideas and algorithms

According to the rules of score calculation ,$\text{“()"}$ My score is $1$, In the case of string splicing, the scores are calculated for each primitive , In the case of nested brackets, the score is calculated according to the number of nested levels .

For string splicing , Just calculate the score for each primitive , Don't need special treatment .

For the case of nested parentheses , Only $\text{“()"}$（ A continuous pair of left and right parentheses ） Will contribute to the score , The score is determined by the number of layers . Definition $\text{“()"}$ The number of layers of is the number of unmatched left parentheses on the left or the number of unmatched right parentheses on the right , for example $\text{“()(()(()))"}$ There are three pairs $\text{“()"}$, Each pair from left to right $\text{“()"}$ The depth of is $0$、$1$、$2$. When $\text{“()"}$ The number of layers is $\text{level}$ when , Its contribution to the score is $2^{\text{level}}$.

The following solution can be obtained ： Number of layers $\text{level}$ Initialize to $0$, Traversing the string from left to right $s$, encounter $\text{‘(’}$ Will $\text{level}$ Add $1$, encounter $\text{‘)’}$ Will $\text{level}$ reduce $1$, When you meet $\text{“()"}$ when , take $2^{\text{level}}$ Add to the score , After traversal, you can get the string $s$ The scores of .

Code

class Solution {
    
    public int scoreOfParentheses(String s) {
    
        int score = 0, level = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
    
            if (s.charAt(i) == '(') {
    
                level++;
            } else {
    
                level--;
                if (s.charAt(i - 1) == '(') {
    
                    score += 1 << level;
                }
            }
        }
        return score;
    }
}

Complexity analysis

• Time complexity ：$O(n)$, among $n$ Is string $s$ The length of . Need to traverse the string $s$ once , The calculation time at each subscript is $O(1)$.

• Spatial complexity ：$O(1)$.