Approach #1: Recursion [Accepted]
Intuition and Algorithm
Write a function parse
that parses the formula from index i
, returning a map count
from names to multiplicities (the number of times that name is recorded).
We will put i
in global state: our parse
function increments i
throughout any future calls to parse
.

When we see a
'('
, we will parse whatever is inside the brackets (up to the closing ending bracket) and add it to our count. 
Otherwise, we should see an uppercase character: we will parse the rest of the letters to get the name, and add that (plus the multiplicity if there is one.)

At the end, if there is a final multiplicity (representing the multiplicity of a bracketed sequence), we'll multiply our answer by this.
Complexity Analysis

Time Complexity: , where is the length of the formula. It is to parse through the formula, but each of multiplicities after a bracket may increment the count of each name in the formula (inside those brackets), leading to an complexity.

Space Complexity: . We aren't recording more intermediate information than what is contained in the formula.
Approach #2: Stack [Accepted]
Intuition and Algorithm
Instead of recursion, we can simulate the call stack by using a stack of count
s directly.
Complexity Analysis
 Time Complexity , and Space Complexity . The analysis is the same as Approach #1.
Approach #3: Regular Expressions [Accepted]
Intuition and Algorithm
Whenever parsing is involved, we can use regular expressions, a language for defining patterns in text.
Our regular expression will be "([AZ][az]*)(\d*)(\()(\))(\d*)"
. Breaking this down by capture group, this is:
([AZ][az]*)
Match an uppercase character followed by any number of lowercase characters, then ((\d*)
) match any number of digits. OR,
(\()
match a left bracket or(\))
right bracket, then(\d*)
match any number of digits.
Now we can proceed as in Approach #2.

If we parsed a name and multiplicity
([AZ][az]*)(\d*)
, we will add it to our current count. 
If we parsed a left bracket, we will append a new
count
to our stack, representing the nested depth of parentheses. 
If we parsed a right bracket (and possibly another multiplicity), we will multiply our deepest level
count
,top = stack.pop()
, and add those entries to our current count.
Complexity Analysis
 Time Complexity , and Space Complexity . The analysis is the same as Approach #1, as this regular expression did not look backwards when parsing.
Analysis written by: @awice. Approaches #1 and #2 inspired by @zestypanda. Java solution for #3 by @jianchao.li.fighter.