7
\$\begingroup\$

Is it possible to improve this code in terms of efficiency / line number ? (avoid nested code ...). It comes from a test I failed. I don't know how I could have done it better.

from collections import Counter

def parse_molecule(molecule):

    array = [[]]

    for token in map(str, molecule):
        if token.isalpha() and token.istitle():
            last = [token]
            upper = token
            array[-1].append(token)
        elif token.isalpha():
            last = upper + token
            array[-1] = [last]
        elif token.isdigit():
            array[-1].extend(last*(int(token)-1))
        elif token == '(' or token == '[':
            array.append([])
        elif token == ')' or token == ']':
            last = array.pop()
            array[-1].extend(last)

    return dict(Counter(array[-1]))

Examples of function usage are following:

>>> water = 'H2O'
>>> parse_molecule(water)
>>>{'H': 2, 'O': 1}

>>> magnesium_hydroxide = 'Mg(OH)2'
>>> parse_molecule(magnesium_hydroxide)
>>> {'Mg': 1, 'O': 2, 'H': 2}

>>> fremy_salt = 'K4[ON(SO3)2]2'
>>> parse_molecule(fremy_salt)
>>> {'K': 4, 'O': 14, 'N': 2, 'S': 4}

This is the statement:

For a given chemical formula represented by a string, count the number of atoms of each element contained in the molecule and return a dict.

For example:

water = 'H2O'
parse_molecule(water)
return {'H': 2, 'O': 1}

magnesium_hydroxide = 'Mg(OH)2'<br>
parse_molecule(magnesium_hydroxide)<br>
return {'Mg': 1, 'O': 2, 'H': 2}

fremy_salt = 'K4[ON(SO3)2]2'<br>
parse_molecule(fremy_salt)<br>
return {'K': 4, 'O': 14, 'N': 2, 'S': 4}

As you can see, some formulas have brackets in them. The index outside the brackets tells you that you have to multiply count of each atom inside the bracket on this index. For example, in Fe(NO3)2 you have one iron atom, two nitrogen atoms and six oxygen atoms.

Note that brackets may be round, square or curly and can also be nested. Index after the braces is optional.

\$\endgroup\$
  • 1
    \$\begingroup\$ Just to clarify, while you may have failed the test, does this function work as intended? \$\endgroup\$ – Graipher Nov 19 '19 at 9:59
  • 1
    \$\begingroup\$ I'm not sure it does, since it does neither ensure the correct brackets nor that all brackets are closed. Try the non-sensical inputs "(H]2" and "(HO2". At least "HO)2" raises an IndexError. \$\endgroup\$ – Graipher Nov 19 '19 at 10:02
  • 1
    \$\begingroup\$ Please update your function to cover cases mentioned in previous comments. Otherwise it's premature to review it as a "working" solution. \$\endgroup\$ – RomanPerekhrest Nov 19 '19 at 10:26
  • 2
    \$\begingroup\$ Li2 apparently contains one atom of Li, one of L, and one of i... \$\endgroup\$ – Peter Taylor Nov 19 '19 at 14:53
  • 2
    \$\begingroup\$ People, can I have your attention please. If the code is improperly tested, that's too bad. But it is tested (badly) and OP was not aware of the code being awfully broken when posting. Per our current scope, that means the code is not off-topic and you lot could've been pointing this out in answers instead. Thank you, have a nice day. \$\endgroup\$ – Mast Nov 19 '19 at 19:12
9
\$\begingroup\$

This code is confusing and inefficient:

for token in map(str, molecule):

It treats molecule as some kind of iterable object, and applies the str function to each element the iteration returns, an assigns each result successively to token. In this case, molecule is a string, which is already a sequence of iterable characters, and a single character is itself a string, so this map function is taking individual character strings and calling str() on those character strings to return the same character strings.

The statement could be written much simpler:

for token in molecule:

These statements are testing for only 2 of the three grouping brackets:

    elif token == '(' or token == '[':
        ...
    elif token == ')' or token == ']':
        ...

The correct statements would read:

    elif token == '(' or token == '[' or token == '{':
        ...
    elif token == ')' or token == ']' or token == '}':
        ...

however, this is rather verbose. You can use the in operator to check if a character appears anywhere in a string, so these test could be written more compactly as:

    elif token in '([{':
        ...
    elif token in ')]}':
        ...

isdigit() is not the best function to use to verify a string can be parsed as an integer. It includes superscript and subscript digits, and other characters which will cause an exception when passed into int(...):

>>> "³₂".isdigit()
True

Instead, use isdecimal().


As mention by scnerd in their answer, it is hard to parse strings character by character. You are detecting a lower case letter, adding it to the last token you found, and replacing the last token. You would need to do the same thing when you find a digit, and only when the current series of digits end perform the replication of the last radical, but this results in numerous special cases, which again make the parsing hard.

It is better to break the molecule into low level tokens, not individual characters, and process complete tokens. As mention by scnerd, the regular expression engine can help. They diverted into attempt to match parenthesis in the regular expression parsing, which complicates things far too much. Here is a simpler approach:

import re

def tokenize_molecule(molecule):
    return re.findall('[A-Z][a-z]?|\d+|.', molecule)

molecules = ['H2O', 'Mg(OH)2', 'K4[ON(SO3)2]2', 'C12H22O11']

for molecule in molecules:
    print(molecule)
    print("\t", tokenize_molecule(molecule))

which outputs:

H2O
     ['H', '2', 'O']
Mg(OH)2
     ['Mg', '(', 'O', 'H', ')', '2']
K4[ON(SO3)2]2
     ['K', '4', '[', 'O', 'N', '(', 'S', 'O', '3', ')', '2', ']', '2']
C12H22O11
     ['C', '12', 'H', '22', 'O', '11']

Here, the regex has 3 parts: [A-Z][a-z]? which matches an element, \d+, which matches one or more digits, and . which matches any character. These are joined together with the | alternative operator; if the current character does not begin an element name, or a digit group, it is returned as a single character ... which is one of the bracket characters in a properly formed molecule.

Using this initial parsing will make the parsing the molecule much easier:

def parse_molecule(molecule):

    # ... 

    for token in re.findall('[A-Z][a-z]?|\d+|.', molecule):

        if token.isalpha():
            # ...
        elif token.isdecimal():
            count = int(token)
            # ...
        elif token in '([{':
            # ...
        elif token in ')]}':
            # ...
        else:
            raise ValueError('Unrecognized character in molecule')

    # ...
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for the explanation, it is very helpfull and I now understand the mistakes I did \$\endgroup\$ – a.cou Nov 20 '19 at 8:43
4
\$\begingroup\$

Just to pull a few of the comments together:

  • This doesn't handle multi-digit numbers properly.

  • This doesn't validate parentheses "()" and brackets "[]", and doesn't handle braces at all "{}".

That said, making this code faster and making this code more correct go hand-in-hand, so forgive me if this answer breaks the Code Review standards a bit and attempts to correct your code while showing how to make it faster, simpler, and more elegant.

Writing your own parser can be very hard, and doing it character-by-character is basically impossible to do correctly unless you've done this kind of thing a lot before. That said, you should look into text parsing tools, libraries, and techniques. Two main tools come to mind: regular expressions, and shift-reduce parsing. The latter is well worth understanding (IMO), but you can likely escape with just regular expressions for this task with just a little support code, since they're powerful enough to handle everything except parenthesis validation, which we'll try to sneak back in.

First off, don't handle individual characters. We can create a simple regular expression pattern that'll peel apart the individual atoms. To start with, let's not worry about parentheses. Every atom begins with an upper case letter: [A-Z]. It may be followed by one or zero lower-case letter: [a-z]?. This pattern may be followed by an integer, which is comprised of any number of digits: either \d* or (\d+)?, which will match the same patterns, but represent them in slightly different ways. This gives us the following regex (I'll group the atom name and number separately: ([A-Z][a-z]?)(\d*).

In [1]: import re

In [2]: strings = [
   ...: 'H',
   ...: 'He',
   ...: 'H2O',
   ...: 'CO2',
   ...: 'Cu2O',
   ...: 'C12H22O11'
   ...: ]

In [3]: for s in strings:
   ...:     print(re.findall(r'([A-Z][a-z]?)(\d*)', s))
   ...:
[('H', '')]
[('He', '')]
[('H', '2'), ('O', '')]
[('C', ''), ('O', '2')]
[('Cu', '2'), ('O', '')]
[('C', '12'), ('H', '22'), ('O', '11')]

Looking pretty good so far, and the code is REALLY simple! Now we just need to handle parentheses. Unfortunately, it's a provable mathematical fact that regular expressions cannot properly handle the parentheses pairing problem. Why should that stop us, though!? We'll detect parentheses pairs from the inside-out, save the results off into arrays like you already do, and work our way out. No biggie!

To do this, we'll create another regex that will find an un-interrupted parenthesis pair and extract the contents and, if it exists, an integer following it. This regex looks really convoluted and only handles "()", not brackets or braces (though the change to do so is trivial), but it demonstrates the idea, and once you understand it, it's actually pretty straightforward:

In [1]: re.search(r'\(([^\(\[\{\)\]\}]+)\)(\d*)', 'ABC(XYZ)5').groups()
Out[1]: ('XYZ', '5')

\( matches the opening parenthesis. ([^...]+) selects one or more characters that AREN'T specified and saves the content into the first group, so we specify all parentheses, brackets, and braces, \(\[\{\)\]\}. We then match the closing parenthesis, \), then a trailing integer if it's there, (\d*). To match a pair of brackets or braces, just change \( to \[ or \{, along with the corresponding \).

The .search function returns an object that tells you where in the searched string 'ABC(XYZ)5' it found the match. You can now extract it from the outer string, parse its guts 'XYZ' using the first regex, since we've guaranteed that this string contains no parentheses of its own, multiply by the integer, and repeat this process, working our way from the inner-most parenthesis pair out. Dealing with nesting is not quite trivial with this approach, but I'm sure you can make it work with a little extra cleverness. The proper general tool to parse text with things like parentheses would be to write a shift-reduce parser, but that becomes a whole new level of complicated, and isn't necessary for this simple task.

This approach, using regular expressions, fits what you're asking about:

  • Fast: Regexes are stupid fast for simple cases like this.

  • Short: The iteration, grouping, etc. are largely handled by the re library and its classes, it's really easy to do complex pattern matching with one-liners.

  • Explicit: Building this solution on regexes makes explicit what you're matching/looking for and what you're missing. Fixing minor issues (like multi-digit numbers, etc.) or finding new, but similar, patterns generally becomes trivial.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you, this is very helpfull ! \$\endgroup\$ – a.cou Nov 20 '19 at 8:29
  • \$\begingroup\$ "Unfortunately, it's a provable mathematical fact that regular expressions cannot properly handle the parentheses pairing problem." A vanishingly small percentage of regex libraries limits itself to regular expressions. The relevant statement would be that Python regexes don't have extensions for recursion (as in Perl5 and Ruby) or balancing groups (and in .Net). \$\endgroup\$ – Peter Taylor Nov 20 '19 at 9:12
3
\$\begingroup\$

To add to AJNeufeld's answer, the regular expression scanner already knows which group matched. The matching group is available in the match object. Giving the groups names and using re.finditer() let's you write code like:

pattern = re.compile(r"""
              (?P<element>[A-Z][a-z]?)
             |(?P<number>\d+)
             |(?P<bracket>[](){}[])
             |(?P<other>.)
             """, re.VERBOSE)


for token in pattern.finditer(molecule):
    if not token:
        ...error...

    if token['element']:
        ...

    elif token['number']:     # <-- this syntax available as of Python 3.6
        ...

    elif token['bracket']:
        ...
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The regex [](){}[] could use some demystification in your post. It is a character set regular expression [...] containing any one of the following characters ] ( ) { } [. Since the ] character normally terminates the set definition, and an empty set is useless as a character set, starting the character set with that character includes it in the regex set, instead of closing the set, and it terminates at the second ] character. \$\endgroup\$ – AJNeufeld Nov 20 '19 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.