给定一个化学式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只包含字母、数字和圆括号，并且题目中给定的是合法的化学式。

解题思路：//使用递归返回hashmap进行拼接

class Solution {
    public String countOfAtoms(String formula) {
        StringBuilder sb=new StringBuilder();
        HashMap<String,Integer> map=dfs(formula);
        ArrayList<String> list=new ArrayList<>(map.keySet());
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String s, String t1) {
                return s.compareTo(t1);
            }
        });
        for(int i=0;i<list.size();i++){
            String str=list.get(i);
            int tt=map.get(str);
            sb.append(str);
            if(tt>1) sb.append(String.valueOf(tt));
        }
        return sb.toString();
    }

    private HashMap<String,Integer> dfs(String formula) {
        HashMap<String,Integer> map=new HashMap<>();
        int i=0;
        while(i<formula.length()){
            if(formula.charAt(i)=='('){
                int j=i+1;
                int label=0;
                while(j<formula.length()){
                    if((formula.charAt(j)==')')&&(label==0))  break;
                    if(formula.charAt(j)==')')  label--;
                    if(formula.charAt(j)=='(')  label++;
                    j++;
                }
                HashMap<String, Integer> ma = dfs(formula.substring(i + 1, j));
                int[] s1=findNumber(j+1,formula);
                i=j+1+s1[1];
                //进行处理
                for (Iterator iterator=ma.entrySet().iterator();iterator.hasNext();){
                    Map.Entry<String,Integer> next =(Map.Entry<String,Integer>) iterator.next();
                    map.put(next.getKey(),map.getOrDefault(next.getKey(),0)+next.getValue()*s1[0]);
                }
            }else{
                String name=findName(i,formula);
                i=i+name.length();
                int[] sum=findNumber(i,formula);
                if(!map.containsKey(name)) map.put(name,sum[0]);
                else map.put(name,map.get(name)+sum[0]);
                i=i+sum[1];
            }

        }
        return map;
    }
    private String findName(int i1,String formula){
        int i=i1;
        for(;i<formula.length();i++){
            if((formula.charAt(i)>='0')&&(formula.charAt(i)<='9')){
                break;
            }
            if(formula.charAt(i)=='('){
                break;
            }
            if(i==i1) continue;
            if((formula.charAt(i)>='A')&&(formula.charAt(i)<='Z')){
                break;
            }
        }
        return formula.substring(i1,i);
    }
    private int[] findNumber(int i1,String formula){
        int i=i1;
        for(;i<formula.length();i++){
            if(!((formula.charAt(i)>='0')&&(formula.charAt(i)<='9'))){
                break;
            }
        }
        if(i==i1)  return new int[]{1,0};
        return new int[]{Integer.valueOf(formula.substring(i1,i)),i-i1};
    }
}