# Python solution using recursion and regex

• A given formula can either start with '(' or an atom.
case 1: If it starts with an atom, then we extract the starting atom and its count using regex and handle the rest of the formula recursively
case 2: If it starts with a '(', then we find the matching ')' and use recursion twice
a) First we solve the sub formula inside '(' ')' using recursion and we extract the count following it and update the counts.
b) Then for the remainder of the formula we make a recursive call to solve it.

``````    def countOfAtoms(self, formula):
res_dict = defaultdict(int)
self.count_rec(formula, res_dict)
return ''.join(chain.from_iterable([[atom, str(res_dict[atom]) if res_dict[atom] > 1 else ''] for atom in sorted(res_dict.keys())]))

def count_rec(self, formula, res):
if formula is None or len(formula) == 0:
return
if formula[0] == '(':
count, i = 1, 1
while count != 0:
if formula[i] == '(': count += 1
if formula[i] == ')': count -= 1
i += 1
temp_res = defaultdict(int)
self.count_rec(formula[1:i-1], temp_res)
num = re.findall('^\d+', formula[i:])
if len(num) > 0:
num = int(num[0])
i += len(str(num))
else:
num = 1
for atom in temp_res:
res[atom] += temp_res[atom] * num
self.count_rec(formula[i:], res)
else:
atom = re.findall('[A-Z][a-z]*', formula)[0]
num = re.findall('^\d+', formula[len(atom):])
num = int(num[0]) if len(num) > 0 else 1
res[atom] += num
self.count_rec(formula[len(atom) + (0 if num == 1 else len(str(num))):], res)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.