递归下降法

class Solution {
    public String countOfAtoms(String formula) {
        Map<String, Integer> map = new TreeMap<>();
        dfs(formula.toCharArray(), 0, map);
        StringBuilder sb = new StringBuilder();
        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            sb.append(entry.getKey() + (entry.getValue() > 1 ? entry.getValue() : ""));
        }
        return sb.toString();
    }
    private int parseDigit(char[] chars, int i, StringBuilder sb) {
        while(i < chars.length && Character.isDigit(chars[i])) {
            sb.append(chars[i++]);
        }
        if(sb.length() == 0) {
            sb.append(1);
        }
        return i;
    }
    private int parseAtom(char[] chars, int i, StringBuilder sb) {
        sb.append(chars[i++]);
        while(i < chars.length && Character.isLowerCase(chars[i])) {
            sb.append(chars[i++]);
        }
        return i;
    }
    private int dfs(char[] chars, int i, Map<String, Integer> map) {
        while(i < chars.length) {
            if(chars[i] == ')') {
                return i + 1;
            }else if(chars[i] == '(') {
                Map<String, Integer> innerMap = new HashMap<>();
                i = dfs(chars, i + 1, innerMap);
                StringBuilder sb = new StringBuilder();
                i = parseDigit(chars, i, sb);
                int cnt = Integer.parseInt(sb.toString());
                innerMap.forEach((key, value) -> {
                    map.put(key, map.getOrDefault(key, 0) + value * cnt);
                });
            }else {
                StringBuilder atom = new StringBuilder();
                StringBuilder digit = new StringBuilder();
                i = parseAtom(chars, i, atom);
                i = parseDigit(chars, i, digit);
                map.put(atom.toString(), map.getOrDefault(atom.toString(), 0) + Integer.parseInt(digit.toString()));
            }
        }
        return i;
    }
}