Solution to leetcode problem 856: Score of parentheses

In this Leetcode problem, we are given a balance parentheses string. That roughly means that each opening parenthesis is matched with exactly one closing parenthesis placed after the opening parenthesis. This way we won’t have illegal strings such as ()) or )(())(.

We are given a recursive definition of String score:

• score( () ) = 1 (base case)
• score( (A) ) = 2 * score( A )
• score( AB ) = score( A ) + score( B )

The first observation to do with balance parentheses strings. They can be represented better by trees. The key is to see that a matching pair of parentheses represent a tree and all parentheses between these 2 represent all the children. Also, not that the string() would be represented by a leaf.

( (child A) (child B) (child C) ) is represented by the tree:

Tree representation of parentheses string

For instance, example 4 of the problem is "(()(()))" can be represented that way: