Nesting Score

Score a balanced string of square brackets by these rules:

[] scores 1.
XY (two adjacent balanced groups) scores score(X) + score(Y).
[X] (a group wrapping a balanced X) scores 2 * score(X).

Return the total score. The input is always a valid balanced bracket string.

nestingScore(s)

Input format: a string of [ and ].

Examples

"[]"        // → 1
"[][]"      // → 2
"[[]]"      // → 2
"[[][]]"    // → 4

Walkthrough

Thinking it through

The scoring rules are recursive: a group's score depends on what's inside it, and adjacent groups add their scores. That points to tracking "the score accumulated so far at this level of nesting" separately for each level, since an inner group's score must be finalized and folded into its parent's total before the parent continues.

Why you need one accumulator per nesting level

In [[][]], the outer bracket wraps two sibling [] groups. While inside it, you need a running total of siblings seen so far at that level (1 + 1 = 2). That total belongs to the outer level — a different accumulator from whatever would track further nesting inside one of the inner groups. Each level needs its own private running total, combined correctly when it closes.

Building the stack-of-accumulators approach

Each stack entry is the running score for the current level:

Start with a single accumulator at 0 — the outermost total.
On [, push a fresh 0 for the new level.
On ], pop the accumulator for the level that just finished. If it's 0, the group was an empty [] pair — scores 1. If non-zero, it wrapped content scoring X — scores 2 * X. Either way, add that into the new top of the stack, the parent's accumulator.
After the whole string, only the original outermost accumulator remains — the sum of every top-level sibling's score, the answer.

Why this correctly implements the recursive rules without recursion

The two rules — wrapping doubles, adjacency adds — are naturally recursive, and a recursive parser would work too. But the stack-of-accumulators does the same thing iteratively, in one pass, since the stack stands in for the call stack: each push is like entering a nested call for a new group, each pop-and-add-to-parent is like that call returning its result. Any recursive, nested scoring problem can often flatten into a single pass using a stack that holds pending results per nesting level.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.