726 Number of Atoms

726. Number of Atoms

1. Question

Given a chemicalformula(given as a string), return the count of each atom.

An atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.

1 or more digits representing the count of that element may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, H2O and H2O2 are possible, but H1O2 is impossible.

Two formulas concatenated together produce another formula. For example, H2O2He3Mg4 is also a formula.

A formula placed in parentheses, and a count (optionally added) is also a formula. For example, (H2O2) and (H2O2)3 are formulas.

Given a formula, output the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

Example 1:

Input: formula = "H2O"

Output: "H2O"

Explanation:
The count of elements are {'H': 2, 'O': 1}.

Example 2:

Input:
formula = "Mg(OH)2"

Output: "H2MgO2"

Explanation:
The count of elements are {'H': 2, 'Mg': 1, 'O': 2}.

Example 3:

Input:
 formula = "K4(ON(SO3)2)2"

Output: "K4N2O14S4"

Explanation: 
The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.

Note:

All atom names consist of lowercase letters, except for the first character which is uppercase.

The length offormulawill be in the range[1, 1000].

formulawill only consist of letters, digits, and round parentheses, and is a valid formula as defined in the problem.

2. Implementation

(1) Stack

思路: 这题和394很类似，像这些带有匹配括号，括号里有subproblem的题，基本可以用递归或者stack处理。用stack的话，由于题目要求返回的结果要按照atom name升序排序，并且要记录每个atom的数目，所以我们用TreeMap，而stack里放的也是TreeMap. 分三种情况处理:

1. 如果当前字符是'('，则压栈，更新treemap

2. 如果当前字符是')'，将当前map的内容保存到temp这个map，从stack中出栈得到之前的map，然后得到')'后面的数字，如果‘)'后面没有数字，则默认是1，再将数字乘以 temp里atom对应的数目，再将相应的结果放在map里

3. 如果字符不是括号，则分别取得atom的名字和跟在其后的数字。需要注意的是，化学原子名字都是首写是大写字母，如果这个名字长度大于1的话，其后的字母都是小写，根据这个特点，我们可以知道 OH 分别代表 O和H这两个化学元素

class Solution {
    public String countOfAtoms(String formula) {
        if (formula == null || formula.length() == 0) {
            return formula;
        }

        int index = 0;
        Stack<TreeMap<String, Integer>> stack = new Stack<>();
        TreeMap<String, Integer> map = new TreeMap<>();
        int n = formula.length();

        while (index < n) {
            char c = formula.charAt(index);

            if (c == '(') {
                ++index;
                stack.push(map);
                map = new TreeMap<>();
            }
            else if (c == ')') {
                ++index;
                TreeMap<String, Integer> temp = map;
                map = stack.pop();

                // Get the number following ')'
                int count = 0;
                while (index < formula.length() && Character.isDigit(formula.charAt(index))) {
                    count = 10 * count + formula.charAt(index) - '0';
                    ++index;
                }

                // If there is no number, it is default to 1
                count = count == 0 ? 1 : count;

                for (String name : temp.keySet()) {
                    map.put(name, map.getOrDefault(name, 0) + temp.get(name) * count);
                }
            }
            else {
                StringBuilder name = new StringBuilder();
                // Get the first letter (Capital)
                name.append(formula.charAt(index));
                ++index;

                // If the atom name has lowercase letter, append it to stringbuilder
                while (index < n && Character.isLowerCase(formula.charAt(index))) {
                    name.append(formula.charAt(index));
                    ++index;
                }

                // Get the number of atoms following the atom
                int count = 0;
                while (index < n && Character.isDigit(formula.charAt(index))) {
                    count = 10 * count + formula.charAt(index) - '0';
                    ++index;
                }

                // If there is no number, it is default to 1
                count = count == 0 ? 1 : count;
                map.put(name.toString(), map.getOrDefault(name.toString(), 0) + count);
            }
        }

        StringBuilder res = new StringBuilder();
        for (String name : map.keySet()) {
            res.append(name);
            int count = map.get(name);
            if (count > 1) {
                res.append(count);
            }
        }
        return res.toString();
    }
}

3. Time & Space Complexity

Stack: 时间复杂度O(n)， 空间复杂度O(n)