class039 嵌套类问题的递归解题套路【算法】

package class039;
import java.util.ArrayList;
// 含有嵌套的表达式求值
// 测试链接 : https://leetcode.cn/problems/basic-calculator-iii/
public class Code01_BasicCalculatorIII {
  public static int calculate(String str) {
    where = 0;
    return f(str.toCharArray(), 0);
  }
  public static int where;
  // s[i....]开始计算，遇到字符串终止 或者 遇到)停止
  // 返回 : 自己负责的这一段，计算的结果
  // 返回之间，更新全局变量where，为了上游函数知道从哪继续！
  public static int f(char[] s, int i) {
    int cur = 0;
    ArrayList<Integer> numbers = new ArrayList<>();
    ArrayList<Character> ops = new ArrayList<>();
    while (i < s.length && s[i] != ')') {
      if (s[i] >= '0' && s[i] <= '9') {
        cur = cur * 10 + s[i++] - '0';
      } else if (s[i] != '(') {
        // 遇到了运算符 + - * /
        push(numbers, ops, cur, s[i++]);
        cur = 0;
      } else {
        // i (.....)
        // 遇到了左括号！
        cur = f(s, i + 1);
        i = where + 1;
      }
    }
    push(numbers, ops, cur, '+');
    where = i;
    return compute(numbers, ops);
  }
  public static void push(ArrayList<Integer> numbers, ArrayList<Character> ops, int cur, char op) {
    int n = numbers.size();
    if (n == 0 || ops.get(n - 1) == '+' || ops.get(n - 1) == '-') {
      numbers.add(cur);
      ops.add(op);
    } else {
      int topNumber = numbers.get(n - 1);
      char topOp = ops.get(n - 1);
      if (topOp == '*') {
        numbers.set(n - 1, topNumber * cur);
      } else {
        numbers.set(n - 1, topNumber / cur);
      }
      ops.set(n - 1, op);
    }
  }
  public static int compute(ArrayList<Integer> numbers, ArrayList<Character> ops) {
    int n = numbers.size();
    int ans = numbers.get(0);
    for (int i = 1; i < n; i++) {
      ans += ops.get(i - 1) == '+' ? numbers.get(i) : -numbers.get(i);
    }
    return ans;
  }
}

package class039;
// 含有嵌套的字符串解码
// 测试链接 : https://leetcode.cn/problems/decode-string/
public class Code02_DecodeString {
  public static String decodeString(String str) {
    where = 0;
    return f(str.toCharArray(), 0);
  }
  public static int where;
  // s[i....]开始计算，遇到字符串终止 或者 遇到 ] 停止
  // 返回 : 自己负责的这一段字符串的结果
  // 返回之间，更新全局变量where，为了上游函数知道从哪继续！
  public static String f(char[] s, int i) {
    StringBuilder path = new StringBuilder();
    int cnt = 0;
    while (i < s.length && s[i] != ']') {
      if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
        path.append(s[i++]);
      } else if (s[i] >= '0' && s[i] <= '9') {
        cnt = cnt * 10 + s[i++] - '0';
      } else {
        // 遇到 [ 
        // cnt = 7 * ? 
        path.append(get(cnt, f(s, i + 1)));
        i = where + 1;
        cnt = 0;
      }
    }
    where = i;
    return path.toString();
  }
  public static String get(int cnt, String str) {
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < cnt; i++) {
      builder.append(str);
    }
    return builder.toString();
  }
}

package class039;
import java.util.TreeMap;
// 含有嵌套的分子式求原子数量
// 测试链接 : https://leetcode.cn/problems/number-of-atoms/
public class Code03_NumberOfAtoms {
  public static String countOfAtoms(String str) {
    where = 0;
    TreeMap<String, Integer> map = f(str.toCharArray(), 0);
    StringBuilder ans = new StringBuilder();
    for (String key : map.keySet()) {
      ans.append(key);
      int cnt = map.get(key);
      if (cnt > 1) {
        ans.append(cnt);
      }
    }
    return ans.toString();
  }
  public static int where;
  // s[i....]开始计算，遇到字符串终止 或者 遇到 ) 停止
  // 返回 : 自己负责的这一段字符串的结果，有序表！
  // 返回之间，更新全局变量where，为了上游函数知道从哪继续！
  public static TreeMap<String, Integer> f(char[] s, int i) {
    // ans是总表
    TreeMap<String, Integer> ans = new TreeMap<>();
    // 之前收集到的名字，历史一部分
    StringBuilder name = new StringBuilder();
    // 之前收集到的有序表，历史一部分
    TreeMap<String, Integer> pre = null;
    // 历史翻几倍
    int cnt = 0;
    while (i < s.length && s[i] != ')') {
      if (s[i] >= 'A' && s[i] <= 'Z' || s[i] == '(') {
        fill(ans, name, pre, cnt);
        name.setLength(0);
        pre = null;
        cnt = 0;
        if (s[i] >= 'A' && s[i] <= 'Z') {
          name.append(s[i++]);
        } else {
          // 遇到 (
          pre = f(s, i + 1);
          i = where + 1;
        }
      } else if (s[i] >= 'a' && s[i] <= 'z') {
        name.append(s[i++]);
      } else {
        cnt = cnt * 10 + s[i++] - '0';
      }
    }
    fill(ans, name, pre, cnt);
    where = i;
    return ans;
  }
  public static void fill(TreeMap<String, Integer> ans, StringBuilder name, TreeMap<String, Integer> pre, int cnt) {
    if (name.length() > 0 || pre != null) {
      cnt = cnt == 0 ? 1 : cnt;
      if (name.length() > 0) {
        String key = name.toString();
        ans.put(key, ans.getOrDefault(key, 0) + cnt);
      } else {
        for (String key : pre.keySet()) {
          ans.put(key, ans.getOrDefault(key, 0) + pre.get(key) * cnt);
        }
      }
    }
  }
}