Problem 243674 · medium · Phase 02 Linear Data Structures

Value of Nested Boxes

stacks · recursion · parsing

A balanced string of ( and ) describes boxes nested inside boxes. Its value is defined by three rules:

  • () (an empty box) is worth 1;
  • two boxes side by side, AB, are worth value(A) + value(B);
  • a box wrapped around contents, (A), is worth 2 * value(A).

Return the value of the string s.

Examples

Input:  s = "(()(()))"
Output: 6
Explanation: (() (())) = 2 * (1 + 2 * 1) = 6.

Input:  s = "()()"
Output: 2

Input:  s = "(())"
Output: 2

Constraints

  • 2 <= len(s) <= 5 * 10**4, s is always balanced
  • Target: O(n) time

Goals

  • Accumulate a score for each open bracket on the stack
  • Combine an inner score into its parent when a bracket closes
Starting Python…