LeetCode: Number of Atoms

This question is asked relatively commonly at both TikTok and Google. Here given the chemical formula as a string, return the count of each atom. The atomic element always starts with an uppercase character then followed by zero or more lowercase letters. One or more digits representing the element's count follow if the count is greater than 1. If a count is 1, no digits will follow since H2O and H2O2 are possible but not H1O2. Two formulas can be concatenated together to produce another formula, H2O2He3Mg4 is also a formula and a formula placed in parentheses is also a formula. Given a formula we want to return all the count of the elements as a string as a first name, followed by its count, followed by the second name, followed by its count, and so on.

Here are explanations and formulas:

H2O is the count of elements {H: 2, O: 1} and Mg(OH)2 with the output of H2MgO2 sing there are 2 H elements, etc. So we want to perform recursion, store the names inside of an ArrayList, and finally, sort these and spit the numbers out in numerical and sequential order. The first approach is recursion, and this means when we see a bracket, parse whatever is in the bracket otherwise we see an uppercase character and parse the rest of the letters. Then if there is a final multiplicity, we'll multiply our answer by this.

Here's the first solution, commented line by line: 

class Solution {

    //this is a marker of the character in the particular word. 

    int i;

    /*

    * This function basically takes in a compound and returns the number of atoms in a particular element in each compound.

    * @parameters: Formula Compound

    * @returns in alphabetical order a compound and the number of elements of an atom in this particular compound

    */

    public String countOfAtoms(String formula) {

        //this indicates a new Stringbuilder

        StringBuilder ans = new StringBuilder();

        //start at the beginning of the string.

        i = 0;

        //have a list of elements and the number of atoms

        Map<String, Integer> count = parse(formula);

        //concatenate string and number in order

        for (String name: count.keySet()) {    

            ans.append(name);

            int multiplicity = count.get(name);

            if(multiplicity > 1) ans.append("" + multiplicity);

        }

        //return string with elements and count of element.

        return new String(ans);

    }

       /*

    * This function parses through and generates a map between the element and the count of the element

    * @parameters: Formula Compound

    * @return a map of an element and number of atoms inside the element combination.

    */

    public Map<String, Integer> parse(String formula) {

        //length of the entire equation 

        int N = formula.length(); 

        //hashmap

        Map<String, Integer> count = new TreeMap();

        // go until the first ')' sign

        while(i < N && formula.charAt(i) != ')') {

            // if we see the first parentheses

            if(formula.charAt(i) == '(') {

                i++;

                //for every map entry recursively parse things inside the entry, parse the rest of the letters.

                for(Map.Entry<String, Integer> entry: parse(formula).entrySet()) {

        count.put(entry.getKey(), count.getOrDefault(entry.getKey(), 0) + entry.getValue());

} else {

    //get to the beginning of the substring.

    int iStart = i++;

    //advance further if there are lowercase characters. 

    while(i < N && Character.isLowerCase(formula.charAt(i))) i++;

    int multiplicity = iStart < i ? Integer.parseInt(formula.substring(iStart, i)) : 1;

    count.put(name, count.getOrDefault(name, 0) + multiplicity);

}

            }

    //start at the character after the initial few ones

    int iStart = ++i;

    //go through the count of the character amount

    while(i < N && Character.isDigit(formula.charAt(i)))) i++;

    //go through all of the characters

    if(iStart < i) {

        //parse through the integer of the substring as the multiplier

        int multiplicity = Integer.parseInt(formula.substring(iStart, i));

        //multiply all the numbers by this factor

        for(String key : count.keySet()) {

            count.put(key, count.get(key) * multiplicity);

    }

    

        }

    //return the given hashmap.

    return count;

    }

}            

The third algorithm is the regular expression algorithm. We can use regular expressions whenever parsing. We want to match uppercase letters followed by any number of lowercase letters than digits or matching a left bracket following a right bracket. If we parse the name with the letters and numbers, add this into the current count, and do the same if we parsed the left bracket. If we parse a left bracket, we append a count to the stack, but if we parse the right bracket we multiply the deepest level count and add these entries to the current count. Here's the final code: 

//regex library

import java.util.regex.*;

class Solution {

    /*

    * This function takes in a compound and returns the number of atoms in a particular element in each compound.

    * @parameters: Formula Compound

    * @returns in alphabetical order a compound and the number of elements of an atom in this particular compound

    */

    public String countOfAtoms(String formula) {

        //element nume with number and parentheses.

         Matcher matcher = Pattern.compile("([A-Z][a-z]*)(\\d*)|(\\()|(\\ (\\d*)").matcher(formula);

    //initialize a stack of HashMap

    Stack<Map<String, Integer>> stack = new Stack();

    //push an empty HashMap onto the stack 

    stack.push(new TreeMap());

    while(matcher.find()) {

        String match = matcher.group();

        //see if there is a match what opens

        if(match.equals("(")) { 

            //push a new element inside of the stack

            stack.push(new TreeMap());

            //this represents the end of a character.

        } else if(match.startsWith(")")) {

            //get top element of the stack

            Map<String, Integer> top = stack.pop();

            //find the number multiplied afterwards 

            int multiplicity = match.length() > 1 ? : Integer.parseInt(match.substring(1, match.length())) : 1;

            //take the element in the stack and multiply these.

            for(String name: top.keySet()) {

                stack.peek().put(name, stack.peek().getOrDefault(name, 0) + top.get(name * multiplicity);

            }

        //case where there is no parentheses.

        } else {

            //start over again. This match is the combination of letters and numbers. We parse the String and integer here. 

            int i = 1;

            //iterate through all the lower case characters

            while(i < match.length() && Character.isLowerCase(match.charAt(i))) {

                    i++;

            }

            //get the name of the element.

            String name = match..substring(0, i);

            //see the number of elements here through parsing.

            int multiplicity = i < match.length() ? Integer.parseInt(match.substring(i, match.length())) : 1;

            //add this into the hashmap content on the current string iteration.

            stack.peek().put(name, stack.peek().getOrDefault(name, 0) + multiplicity);

        }

    }

        //build the final String by sorting all of them and putting it into a string.

        StringBuilder ans = new StringBuilder();

        for(String name: stack.peek().keySet()) {

            ans.append(name);

            final int count = stack.peek().get(name);

            //only append the count if the count is greater than 1, per question.

            if(count > 1) ans.append(String.valueOf(count));

        }

        //return the final string

        return ans.toString();

    }

}