1、题目

image.png

2、分析与解答

由括号的表达式问题：用栈处理。因为括号内部也是一个表达式，且要统计原子的数量，因此栈中元素为 Map 集合。
思路：

  1. 遍历表达式，如果是左括号，则往栈中压入一个空的 map
  2. 如果不是括号，则读取一个原子名称，如果后面还有数字则读取该数字为原子的个数，否则该原子个数为1，将原子和数字加入栈顶的 map 中。
  3. 如果是右括号，读取括号后的数字 num，若没有num 则默认为1，弹出栈顶的map，将原子个数都乘以num，存到目前栈顶的map 中。

  4. 最后栈顶的map 即为所有原子和其对应的个数。遍历存到数组中。

    1. class Solution {
    2.  private String formula;
    3.  private int i;
    4.  private int n;
    5.  public String countOfAtoms(String formula) {
    6.      this.formula = formula;
    7.      this.i = 0;
    8.      this.n = formula.length();
    9.      Deque<HashMap<String,Integer>> deque = new LinkedList<>();
    10.      deque.push(new HashMap<String,Integer>());
    11.      while(i < n) {
    12.          char ch = formula.charAt(i);
    13.          if(ch == '(') {
    14.              i++;
    15.              deque.push(new HashMap<String,Integer>());
    16.          } else if (ch == ')') {
    17.              i++;
    18.              int num = parseNum();
    19.              Map<String,Integer> popMap = deque.pop();
    20.              Map<String,Integer> topMap = deque.peek();
    21.              for(Map.Entry<String,Integer> entry : popMap.entrySet()) {
    22.                  String atom = entry.getKey();
    23.                  int v = entry.getValue();
    24.                  topMap.put(atom,topMap.getOrDefault(atom,0) + v * num);
    25.              }
    26.          } else {
    27.              String atom = parseAtom();
    28.              int num = parseNum();
    29.              Map<String,Integer> topMap = deque.peek();
    30.              topMap.put(atom,topMap.getOrDefault(atom,0) + num);
    31.          }
    32.      }
    33.      Map<String,Integer> popMap = deque.pop();
    34.      TreeMap<String,Integer> treeMap = new TreeMap<>(popMap);
    35.      StringBuilder sb = new StringBuilder();
    36.      for(Map.Entry<String,Integer> entry : treeMap.entrySet()) {
    37.          sb.append(entry.getKey());
    38.          int count = entry.getValue();
    39.          if(count > 1) {
    40.              sb.append(count);
    41.          }
    42.      }
    43.      return sb.toString();
    44.  }
    46.  private String parseAtom() {
    47.      StringBuilder sb = new StringBuilder();
    48.      sb.append(formula.charAt(i++));
    49.      while(i<n && Character.isLowerCase(formula.charAt(i))) {
    50.          sb.append(formula.charAt(i++));
    51.      }
    52.      return sb.toString();
    53.  }
    55.  private int parseNum() {
    56.      if(i == n || !Character.isDigit(formula.charAt(i))) {
    57.          return 1;
    58.      }
    59.      int num = 0;
    60.      while(i < n && Character.isDigit(formula.charAt(i))) {
    61.          num = num * 10 + formula.charAt(i++) - '0';
    62.      }
    63.      return num;
    64.  }
    65. }