Score the brackets
Score a balanced bracket string where a pair holding nothing is worth 1, a pair around something doubles it, and neighbours add, using a stack of partial scores. About 16 minutes.
One running total per open level
The rules are: an empty pair is worth 1, two neighbours add their scores, and a pair around something is worth double what is inside. For (()(())) the inner parts score 1 and 2, add to 3, and double to 6.
Keep a stack of running totals. The bottom is the outermost level, starting at 0. An opener pushes a new total of 0 for the level it starts.
stack = [0]
for ch in s:
if ch == "(":
stack.append(0)Two openers so far. Totals on the stack: 0, 0, 0.
Fold in at each closer
A closer ends the top level. Pop its total, call it inner. Its value is double inner, but at least 1: a pair with nothing inside has inner 0 and is worth 1.
Add that value to the total now on top, which belongs to the group around it. Neighbours add up simply because each adds into the same total.
else:
inner = stack.pop()
stack[-1] += max(2 * inner, 1)
return stack[0]What is the score of the text ( ) ( ) ?
- A2
- B4
- C1
Show the answer
2. Two empty pairs next to each other are 1 plus 1.
Score of parentheses
You are given a balanced string s of round brackets. Its score is defined by these rules: "()" has score 1; if A and B are balanced strings, then AB (A followed by B) has score A + B; and "(A)" has score 2 times the score of A. Return the score of s.
s = "(()(()))" → 6
2 ≤ length of s ≤ 50 · s is a balanced string of ( and )