题目描述

给定一个化学式formula（作为字符串），返回每种原子的数量。

原子总是以一个大写字母开始，接着跟随0个或任意个小写字母，表示原子的名字。

如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。

两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。

一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。

给定一个化学式，输出所有原子的数量。格式为：第一个（按字典序）原子的名子，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。

样例

示例 1:

输入: 
formula = "H2O"
输出: "H2O"
解释: 
原子的数量是 {'H': 2, 'O': 1}。
示例 2:

输入: 
formula = "Mg(OH)2"
输出: "H2MgO2"
解释: 
原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。
示例 3:

输入: 
formula = "K4(ON(SO3)2)2"
输出: "K4N2O14S4"
解释: 
原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。
注意:

所有原子的第一个字母为大写，剩余字母都是小写。
formula的长度在[1, 1000]之间。
formula只包含字母、数字和圆括号，并且题目中给定的是合法的化学式。

算法

(Stack+HashMap) O(n*logn)

涉及到括号匹配的题目，基本要么dfs要么stack，不妨假设用stack来做。

1. 维护一个栈，栈中存放一个Map，表示记录一个括号内原子的名称和原子的数量。当前括号内的Map称为curMap，上层Map维护在stack里面。

2. 扫描原分子式，如果遇到一个原子，则更新名称和其对应的数量的curMap。如果遇到左括号，则老curMap进栈，
重新new 一个curMap。如果遇到右括号，首先备份一个tempmap用来记录本次括号内原子的名称和原子的数量。然后出栈后的Map当作curMap，和之前tempMap做计算，将对应位置上的值乘上括号后的数值，得到最终所有的括号内原子数量，然后更新到curMap。
3. 最后需要将栈中所有原子出栈，并统计每个原子的出现次数，然后排序输出。

思路参考: wzc1995

思路参考wzc1995

Java 代码

class Solution {
    int i = 0;

    public String countOfAtoms(String formula) {
        int n = formula.length();
        Deque<TreeMap<String/**当前括号内的字符**/, Integer/**当前括号内单个字符个数**/>> stack = new ArrayDeque<>(n);
        TreeMap<String, Integer> curMap = new TreeMap<>();
        while (i < n) {
            char ch = formula.charAt(i);
            if (ch == '(') {
                i++;
                stack.push(curMap);
                curMap = new TreeMap<>();
            } else if (ch == ')') {
                // 两个map合并
                i++;
                TreeMap<String, Integer> temp = curMap;
                curMap = stack.pop();
                int cnt = getNum(formula);
                for (Map.Entry<String, Integer> entry : temp.entrySet()) {
                    // "Mg(OH)2"
                    String k = entry.getKey();
                    Integer v = entry.getValue();
                    curMap.put(k, curMap.getOrDefault(k, 0) + v * cnt);
                }
            } else {
                String name = getName(formula);
                int num = getNum(formula);
                curMap.put(name, curMap.getOrDefault(name, 0) + num);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (String name : curMap.keySet()) {
            int quantity = curMap.get(name);
            sb.append(name);
            if (quantity > 1) {
                sb.append(quantity);
            }
        }
        return sb.toString();
    }

    private int getNum(String formula) {
        int n = formula.length();
        if (i == n || !(formula.charAt(i) >= '0' && formula.charAt(i) <= '9')) {
            return 1;
        }

        int cnt = 0;
        while (i < n && (formula.charAt(i) >= '0' && formula.charAt(i) <= '9')) {
            cnt = cnt * 10 + formula.charAt(i) - '0';
            i++;
        }

        return cnt;
    }

    private String getName(String formula) {
        int n = formula.length();
        // 第一个化学元素的大写字符
        StringBuilder name = new StringBuilder();
        name.append(formula.charAt(i));
        i++;

        // 余下化学元素的小写字符
        while (i < n && formula.charAt(i) >= 'a' && formula.charAt(i) <= 'z') {
            name.append(formula.charAt(i));
            i++;
        }
        return name.toString();
    }
}