726. Number of Atoms

Problem Explanation

This problem asks to count the number of atoms in a given chemical formula. A chemical formula can consist of a single element with or without a count (e.g. "O" or "O2"), two elements concatenated together (e.g. "H2O"), or a formula placed in parentheses with an optional count (e.g. "(H2O2)" or "(H2O2)3").

The program should break down the formula into its constituent elements and their counts. The output should be a string with each element and its count (if more than 1) in alphabetical order.

For instance, if the input is "H2O", the program should return "H2O" because there are 2 Hydrogen atoms and 1 Oxygen atom. Similarly, if the input is "Mg(OH)2", the program should return "H2MgO2" because there are 2 Hydrogen atoms, 1 Magnesium atom and 2 Oxygen atoms.

Solution Approach

The problem can be proceeded by using recursion and a stack data structure. When we traverse the formula from the left, if we meet an uppercase character, we will parse the rest of the element and add the element and the count to a map. If we meet a '(', we will parse the subformula and multiply the count of all elements in the subformula by the count following the ')'.

Here is how we use recursion and stack. Whenever meet an '(' brace, we create a new stack top and start to trace a new map. When meet a ')' brace, we pop up the map from stack top and merge it into the lower level map. During the process, we need to keep track of the count of each element.

Python Solution

1
2python
3class Solution:
4    def countOfAtoms(self, formula):
5        stack = [collections.Counter()]
6        i = 0
7
8        while i < len(formula):
9            if formula[i] == '(':
10                stack.append(collections.Counter())
11                i += 1
12            elif formula[i] == ')':
13                top = stack.pop()
14                i += 1
15                start = i
16                while i < len(formula) and formula[i].isdigit():
17                    i += 1
18                multiplier = int(formula[start:i] or 1)
19                for name, v in top.items():
20                    stack[-1][name] += v * multiplier
21            else:
22                start = i
23                i += 1
24                while i < len(formula) and formula[i].islower():
25                    i += 1
26                name = formula[start:i]
27                start = i
28                while i < len(formula) and formula[i].isdigit():
29                    i += 1
30                count = int(formula[start:i] or 1)
31                stack[-1][name] += count
32
33        return "".join(name + (str(stack[-1][name]) if stack[-1][name] > 1 else '')
34                       for name in sorted(stack[-1]))

Java Solution

1
2java
3class Solution {
4    public String countOfAtoms(String formula) {
5        int N = formula.length();
6        Stack<Map<String, Integer>> stack = new Stack<>();
7        stack.push(new TreeMap<>());
8
9        for (int i = 0; i < N;) {
10            if (formula.charAt(i) == '(') {
11                stack.push(new TreeMap<>());
12                i++;
13            } else if (formula.charAt(i) == ')') {
14                Map<String, Integer> top = stack.pop();
15                int start = ++i, multiplicity = 1;
16                while (i < N && Character.isDigit(formula.charAt(i))) i++;
17                if (start < i) multiplicity = Integer.parseInt(formula.substring(start, i));
18                for (String c: top.keySet()) {
19                    int v = top.get(c);
20                    stack.peek().put(c, stack.peek().getOrDefault(c, 0) + v * multiplicity);
21                }
22            } else {
23                int start = i++;
24                while (i < N && Character.isLowerCase(formula.charAt(i))) i++;
25                String name = formula.substring(start, i);
26                start = i;
27                while (i < N && Character.isDigit(formula.charAt(i))) i++;
28                int multiplicity = i > start ? Integer.parseInt(formula.substring(start, i)) : 1;
29                stack.peek().put(name, stack.peek().getOrDefault(name, 0) + multiplicity);
30            }
31        }
32
33        StringBuilder ans = new StringBuilder();
34        for (String name: stack.peek().keySet()) {
35            ans.append(name);
36            int multiplicity = stack.peek().get(name);
37            if (multiplicity > 1) ans.append("" + multiplicity);
38        }
39        return new String(ans);
40    }
41}

Javascript Solution

1
2javascript
3var countOfAtoms = function(formula) {
4    let hash = {};
5    let i = 0;
6    let count = 1;
7    let stack = [];
8    let name = "";
9    for (let char of formula) {
10        let code = char.charCodeAt(0);
11        if (65 <= code && code <= 90) {
12            if (name) addName(hash, name, count);
13            name = char;
14            count = 1;
15        } else if (97 <= code && code <= 122) {
16            name += char; 
17        } else if ("0" <= char && char <= "9") {
18            count = count * 10 + parseInt(char);
19        } else if (char === "(") {
20            let newObj = {};
21            stack.push([hash, name, count]);
22            hash = newObj;
23            name = "";
24            count = 1;
25        } else if (char === ")") {
26            if (name) addName(hash, name, count);
27            let oldHash = stack.pop();
28            let outsideCount = 0;
29            while (i + 1 < formula.length && "0" <= formula[i + 1] && formula[i + 1] <= "9") {
30                outsideCount = outsideCount * 10 + parseInt(formula[i + 1]);
31                i++;
32            };
33            if (outsideCount === 0) outsideCount = 1;
34            combine(oldHash[0], hash, name, oldHash[2] * outsideCount);
35            hash = oldHash[0];
36            name = oldHash[1];
37            count = 1;
38        } else { // if char == '-'
39            if (name) addName(hash, name, count);
40            count = 1 - parseInt(char);
41            name = "";
42        };
43        i++;
44    };
45    if (name) addName(hash, name, count);
46    
47    let result = "";
48    let sortedKeys = Object.keys(hash).sort((a, b) => a.localeCompare(b));
49    for (let sortedKey of sortedKeys) {
50        result += sortedKey;
51        if (hash[sortedKey] > 1) result += hash[sortedKey];
52    };
53    return result;
54};
55
56function addName(hash, name, count) {
57    if (hash[name]) {
58        hash[name] += count;
59    } else {
60        hash[name] = count;
61    };
62};
63
64function combine(hash, oldHash, name, count) {
65    Object.keys(oldHash).forEach(key => {
66        hash[key] = hash[key] + oldHash[key] * count || oldHash[key] * count;
67    })
68};

C++ Solution

1
2c++
3class Solution {
4public:
5    string countOfAtoms(string formula) {
6        int i = 0;
7        map<string, int> counts = parse(formula, i);
8        string ans;
9        for (pair<string, int> p : counts) {
10            ans += p.first;
11            if (p.second > 1)
12                ans += to_string(p.second);
13        }
14        return ans;
15    }
16
17private:
18    map<string, int> parse(string& formula, int& i) {
19        map<string, int> counts;
20        while (i != formula.size() && formula[i] != ')') {
21            if (formula[i] == '(') {
22                i++;  // Skip '('
23                for (auto& p : parse(formula, i)) { counts[p.first] += p.second; }
24            } else {
25                int iStart = i++;
26                while (i != formula.size() && islower(formula[i])) { i++; }
27                string name = formula.substr(iStart, i - iStart);
28                iStart = i;
29                while (i != formula.size() && isdigit(formula[i])) { i++; }
30                int count = iStart == i ? 1 : stoi(formula.substr(iStart, i - iStart));
31                counts[name] += count;
32            }
33        }
34        int iStart = ++i;
35        while (i != formula.size() && isdigit(formula[i])) { i++; }
36        if (iStart < i) {
37           int multiplicity = stoi(formula.substr(iStart, i - iStart));
38           for (auto& p : counts) { p.second *= multiplicity; }
39        }
40        return counts;
41    }
42};

C# Solution

1
2csharp
3public class Solution {
4	public string CountOfAtoms(string formula) {
5		int i = 0, len = formula.Length;
6		Stack<Dictionary<string, int>> stack = new Stack<Dictionary<string, int>>();
7		stack.Push(new Dictionary<string, int>());
8		while (i < len) {
9			if (formula[i] == '(') {
10				stack.Push(new Dictionary<string, int>());
11				i++;
12			} else if (formula[i] == ')') {
13				var top = stack.Pop();
14				int start = ++i, num = 1;
15				while (i < len && Char.IsDigit(formula[i])) i++;
16				if (i > start) num = int.Parse(formula.Substring(start, i - start));
17				foreach (var kvp in top)
18					if (stack.Peek().ContainsKey(kvp.Key)) stack.Peek()[kvp.Key] += kvp.Value * num;
19					else stack.Peek().Add(kvp.Key, kvp.Value * num);
20			} else {
21				int start = i++;
22				while (i < len && Char.IsLower(formula[i])) i++;
23				string name = formula.Substring(start, i - start);
24				start = i;
25				while (i < len && Char.IsDigit(formula[i])) i++;
26				int num = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
27				if (stack.Peek().ContainsKey(name)) stack.Peek()[name] += num;
28				else stack.Peek().Add(name, num);
29			}
30		}
31		var sb = new StringBuilder();
32		var list = stack.Peek().Keys.ToList();
33		list.Sort();
34		foreach (string c in list)
35			sb.Append(c + (stack.Peek()[c] > 1 ? stack.Peek()[c].ToString() : ""));
36		return sb.ToString();
37	}
38}

All these solutions involved employing a stack data structure for handling parentheses and a map for keeping storing the count of the elements. The stack would keep track of the corresponding map that contains the element and its count. If the program encounters an open parentheses or an upper case alphabet that signifies the beginning of a chemical symbol, it either begins by creating a new map or extracts the chemical symbol and its count and stores them into the map. For any closing parentheses, it intelligently reflects the multiplication factor (if any) associated with the chemical compounds enclosed by the parentheses on the corresponding counts, and merges them into a single map.

Any programming language with built-in or library-supported data structures like stack and map like Python, Java, JavaScript, C++ and C# can solve this problem with a similar approach. The differences lie in the syntax, and the way built-in methods are used. The Java solution, for instance, uses the 'peek()' function of the Stack data structure, which is used to look at the top element of the stack without deleting it. The JavaScript solution, on the other hand, extracts the character codes to determine whether a character is uppercase, lowercase, or a number. The C++ solution uses a map instead of counter to track each atom and its counts.

When choosing a language to solve this problem, consider the language’s syntax, available libraries, and runtime performance. For example, Python's collections library provides a Counter class which makes counting convenient, while Java's Stack class provides built-in methods like peek(), push() and pop() which lessen the programmer’s job. JavaScript to determine a character's type by extracting the character code using 'charCodeAt' function which is neat. The performance may also be an important factor as Java and C++ tend to outperform Python and JavaScript in large-scale data manipulation. Evaluating features provided by different languages can guide you to pick the most suitable language for different problems.

Solution Implementation