Parsing A Chemistry Formula In Python

I am trying to solve this problem: https://leetcode.com/articles/number-of-atoms/#approach-1-recursion-accepted. The question is: given a formula like C(Mg2(OH)4)2, return a hash t

Solution 1:

I think you can use recursivity to solve this problem. Here is how your function should work:

• Do like you do in the first code, until you encounter an opening parenthesis.
• When you encounter an opening parenthesis, find the corresponding closing parenthesis. This can be done with a counter: initialize it to 1, then when you encounter a new opening parenthesis, you increment the counter, and when you encounter a closing parenthesis you decrement it. When the counter equals 0, you have found the matching closing parenthesis.
• Cut the string between parentheses and call the same function with this string (here's the recursive aspect).
• Add the values in the returned dictionary to the current dictionary, multiplied by the number which follows the parenthesis.

If you have problems implementing some parts of this solution, tell me and I will give more details.

EDIT: about the stack approach The stack approach just simulates recursivity. Instead of calling the function again and having local counter, it has a stack of counters. When an opening parenthesis is opened, it counts in this context, and when it's closed it merges it with the context which contains it, with corresponding multiplicity.

I prefer by far the recursive approach, which is more natural.

Solution 2:

You may want to Google for python parser generator. A parser generator is a library that helps developers create parsers for any kind of formula or language (technically, any "grammar") without doing all the work from scratch.

You may have to do some reading to understand what type of grammar a chemical formula adheres to.

An interesting overview for Python is this.