Score of Parentheses

Intuitiona closing parenthesis tells you exactly when one score is complete

The score rules describe a tree hidden inside the string. A pair of parentheses creates one group; adjacent groups contribute by addition, while a group wrapped around another contributes twice its inside score. You cannot finish an outer group until every group inside it has been evaluated, so the most recently opened unfinished group must be handled first.

Give every opening parenthesis its own running score, initially zero. A closing parenthesis ends the current group: if its inside score is zero, the group is the primitive pair (), worth 1; otherwise its inside score is doubled. Add that finished value to the surrounding group, because adjacent completed groups are combined by addition.

Approach

1. 1Push a zero before processing the string, because this bottom entry collects the score of all top-level groups and gives every completed group a parent to receive its value.
2. 2For each opening parenthesis, push a new zero, because all characters until its matching close belong to a deeper group and must not immediately change the enclosing score.
3. 3For each closing parenthesis, read and remove the top score, because the top entry represents the group that has just become complete.
4. 4Turn that inner score into max(2 * inner, 1), because a nonempty group is nested and must double its inside score, while an empty pair () has score 1 instead of zero.
5. 5Add the completed value to the new top entry, because the group is now one component of its enclosing group or of the top-level concatenation.
6. 6After every character has been processed, return the bottom entry, because balanced input has closed every group and all scores have flowed back to the sentinel level.

Complexityeach parenthesis changes one stack entry once

Annotated solutionC++ · stack simulation · one entry per open depth

#include <algorithm>
#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> st;
        st.push(0);

        for (char c : s) {
            if (c == '(') {
                st.push(0);
            } else {
                int inside = st.top();
                st.pop();
                int value = max(2 * inside, 1);
                st.top() += value;
            }
        }

        return st.top();
    }
};

The sentinel zero is what makes concatenation work without a special case. For ()(), the first close adds 1 to the sentinel and the second close adds another 1 to the same entry. For (()), the inner close adds 1 to the inner group, and the outer close doubles that result before adding it to the sentinel.

The depth-counting alternativean O(1)-space optimization when only primitive groups need direct scoring

You can avoid the stack because every primitive pair contributes a power of two determined by its nesting depth. When a close follows an opening parenthesis, that pair is exactly (), and its contribution is 2 raised to the depth after the close. A close at depth 0 contributes 1, a close at depth 1 contributes 2, and so on. Other closing parentheses only finish a nonempty group whose contribution was already accounted for by its innermost primitive pairs.

#include <string>
using namespace std;

class Solution {
public:
    int scoreOfParentheses(string s) {
        int depth = 0;
        int score = 0;

        for (int i = 0; i < static_cast<int>(s.size()); ++i) {
            if (s[i] == '(') {
                ++depth;
            } else {
                --depth;
                if (s[i - 1] == '(') {
                    score += 1 << depth;
                }
            }
        }

        return score;
    }
};

This is an optimization, not merely a different arrangement: it reduces extra space from O(n) to O(1), while time remains O(n). The tradeoff is less direct bookkeeping. The stack mirrors the three scoring rules and is easier to adapt if the representation or scoring rules change; the depth version depends on the special power-of-two structure of these parentheses rules.

Common mistakesthe wrong line can still look reasonable on simple samples