給定一個化學式formula（作為字符串），返回每種原子的數量。
原子總是以一個大寫字母開始，接著跟隨0個或任意個小寫字母，表示原子的名字。
如果數量大于 1，原子后會跟著數字表示原子的數量。如果數量等于 1 則不會跟數字。例如，H2O 和 H2O2 是可行的，但 H1O2 這個表達是不可行的。
兩個化學式連在一起是新的化學式。例如 H2O2He3Mg4 也是化學式。
一個括號中的化學式和數字（可選擇性添加）也是化學式。例如 (H2O2) 和 (H2O2)3 是化學式。
給定一個化學式 formula ，返回所有原子的數量。格式為：第一個（按字典序）原子的名字，跟著它的數量（如果數量大于 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}。
示例 4：輸入：formula = "Be32"
輸出："Be32"
解題思路
使用遞歸實現棧的功能
- 當遇到’('時,對括號內的元素進行遞歸
- 當遇到’)'時，攜帶map出棧（map內原子個數還需要乘括號后出現的數字，如果沒有，默認為1），回到上一級函數，并且將返回的map進行合并
- 在遞歸函數中，遇到字母，即需要處理原子，統計個數，使用treemap記錄該原子出現次數
代碼
class Solution {int next=-1;public String countOfAtoms(String formula) {StringBuilder builder = new StringBuilder();Map<String, Integer> map = count(formula, 0);for (Map.Entry<String, Integer> entry : map.entrySet()) {builder.append(entry.getKey()).append(entry.getValue()==1?"":entry.getValue());}return builder.toString();}public Map<String,Integer> merge(Map<String,Integer> a,Map<String,Integer> b) {for (Map.Entry<String,Integer> c:b.entrySet()){a.put(c.getKey(),a.getOrDefault(c.getKey(),0)+c.getValue());}return a;}public Map<String,Integer> count(final String formula, int l) {Map<String, Integer> map = new TreeMap<String, Integer>();for (int i=l;i<formula.length();){if(formula.charAt(i)=='('){Map<String, Integer> count = count(formula, i + 1);merge(map,count);i=next;}else if(formula.charAt(i)==')'){//后面沒有跟數字，默認值是1if(i+1>=formula.length()||!Character.isDigit(formula.charAt(i+1)))//沒有跟數字next=i+1;else {//把數字提取出來i++;int s=i;while (i<formula.length()&&Character.isDigit(formula.charAt(i)))i++;int cur=Integer.parseInt(formula.substring(s,i));map.replaceAll((k,v)->v*cur);next=i;}return map;} else if(Character.isUpperCase(formula.charAt(i))) {
//遇到大寫字母，如果后面有小寫的也歸于此原子int s = i;i++;while (i < formula.length() && Character.isLowerCase(formula.charAt(i)))i++;String key = formula.substring(s, i);int cur;if (i >= formula.length() || !Character.isDigit(formula.charAt(i)))cur = 1;else {s = i;while (i < formula.length() && Character.isDigit(formula.charAt(i)))i++;cur = Integer.parseInt(formula.substring(s, i));}map.put(key, map.getOrDefault(key, 0) + cur);}}return map;}
}
)
