Several Algorithms to Compute the Score of Parentheses

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

Note:

• S is a balanced parentheses string, containing only ( and ).
• 2 <= S.length <= 50

Divide and Conquer via Recursion

This problem is inherent a divide-and-conquer problem that can be solved recursively. The intuitive solution would be to parse the Parentheses string into form of AB or (A). The special case is that when string is () the score is 1, and when string is empty, the score is obviously zero.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int scoreOfParentheses(string S) {
        if (S == "") return 0;
        if (S == "()") return 1;
        int n = S.size();
        int i = 0, k = 0;
        while (i < n) {
            if (S[i] == '(') {
                k ++;
            } else {
                k --;
            }
            // the rightmost matching closed Parentheses 
            if (k == 0) {
                break;
            }
            i ++;
        }
        // get A where A is in (A)
        string ls = S.substr(1, i - 1);        
        // deal with special case (), otherwise recursively compute the score of A
        int left = (ls == "") ? 1 : (2 * scoreOfParentheses(ls));
        // the right substring B, can be computed recursively.
        int right = (i + 1 < n) ? scoreOfParentheses(S.substr(i + 1)) : 0;
        // A+B
        return left + right;            
    }
};

class Solution {
public:
    int scoreOfParentheses(string S) {
        if (S == "") return 0;
        if (S == "()") return 1;
        int n = S.size();
        int i = 0, k = 0;
        while (i < n) {
            if (S[i] == '(') {
                k ++;
            } else {
                k --;
            }
            // the rightmost matching closed Parentheses 
            if (k == 0) {
                break;
            }
            i ++;
        }
        // get A where A is in (A)
        string ls = S.substr(1, i - 1);        
        // deal with special case (), otherwise recursively compute the score of A
        int left = (ls == "") ? 1 : (2 * scoreOfParentheses(ls));
        // the right substring B, can be computed recursively.
        int right = (i + 1 < n) ? scoreOfParentheses(S.substr(i + 1)) : 0;
        // A+B
        return left + right;            
    }
};

The algorithm complexity is O(N^2) where N is the size of the input Parentheses string because in worse cases, the Parentheses can be “(((…)))” so each iteration, it will need to scan the entire string and this falls to the recursively call of (A).

The space complexity is O(N) because we are using the recursion which implies the stack calls.

The following C++ has the same algorithm but is implemented slightly differently without using the substring (string manipulation can be quite costly in C++). Rather, a helper function score takes an addition two paramters of the index range.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int scoreOfParentheses(string S) {
        return score(S, 0, S.size());
    }
 
private:
    int score(string S, int i, int j) {
        int ans = 0, bal = 0;
        for (int k = i; k < j; ++ k) {
            bal += (S[k] == '(') ? 1 : - 1;
            if (bal == 0) {
                if (k - i == 1) {
                    // special case () = 1
                    ans ++;
                } else {
                    // otherwise (A) = 2 * A
                    ans += 2 * score(S, i + 1, k);
                }
                // move cursor to the end of A                    
                i = k + 1;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int scoreOfParentheses(string S) {
        return score(S, 0, S.size());
    }

private:
    int score(string S, int i, int j) {
        int ans = 0, bal = 0;
        for (int k = i; k < j; ++ k) {
            bal += (S[k] == '(') ? 1 : - 1;
            if (bal == 0) {
                if (k - i == 1) {
                    // special case () = 1
                    ans ++;
                } else {
                    // otherwise (A) = 2 * A
                    ans += 2 * score(S, i + 1, k);
                }
                // move cursor to the end of A                    
                i = k + 1;
            }
        }
        return ans;
    }
};

Counting the Cores (Mathematics Algorithm) to Compute the Parentheses Score

We can record the number of left (opening) Parentheses i.e. bal, and when we meet the right (closed) Parentheses, if it is the innermost Parentheses, we increment the answer by 2^(bal-1). For example, ((()))() = 2^2 + 2^0 = 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int scoreOfParentheses(string S) {
        int ans = 0;
        int bal = 0;
        char prev = ' ';
        for (const auto &n: S) {
            if (n == '(') {
                bal ++;
            } else {            
                bal --;
                if (prev == '(') {
                    ans += 1 << bal;
                }
            }
            prev = n;
        }
        return ans;
    }
};

class Solution {
public:
    int scoreOfParentheses(string S) {
        int ans = 0;
        int bal = 0;
        char prev = ' ';
        for (const auto &n: S) {
            if (n == '(') {
                bal ++;
            } else {            
                bal --;
                if (prev == '(') {
                    ans += 1 << bal;
                }
            }
            prev = n;
        }
        return ans;
    }
};

Simple, elegant and most effective solution. This takes O(N) time and constant space.

Parentheses Score Algorithm via Stack

Another solution is to use the stack. At the begining, we push the score 0 to the stack. And everytime we meet a opening Parentheses, we push a zero to the stack, when we meet closing Parentheses, we pop two numbers from the stack, and we compute the current score and push the result back to the stack. The special case has to be dealt with for the case of () which has score of 1.

For example, for (())(), we have:

• initial stack [0]
• stack [0, 0, 0] when we meet two opening Parentheses.
• stack [0, 1] when we meet first “)”, pop two zeros and push the updated score.
• stack [2] when we meet second “)”, the updated score is 0 + 2 * 1
• stack [2, 0] when we have the last “(“
• stack [3], the last “)” gives us updated score 2 + max(2 * 0, 1) = 3

The space complexity is O(N) and the time complexity is O(N) as well.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int scoreOfParentheses(string S) {
        stack<int> st;
        st.push(0);
        for (const auto &n: S) {
            if (n == '(') {
                st.push(0);
            } else {
                int v = st.top();
                st.pop();
                int w = st.top();
                st.pop();
                st.push(w + max(2 * v, 1));
            }
        }
        return st.top();
    }
};

class Solution {
public:
    int scoreOfParentheses(string S) {
        stack<int> st;
        st.push(0);
        for (const auto &n: S) {
            if (n == '(') {
                st.push(0);
            } else {
                int v = st.top();
                st.pop();
                int w = st.top();
                st.pop();
                st.push(w + max(2 * v, 1));
            }
        }
        return st.top();
    }
};

–EOF (The Ultimate Computing & Technology Blog) —