class039 嵌套类问题的递归解题套路
Code1 772. 基本计算器 III
实现一个基本的计算器来计算简单的表达式字符串。
表达式字符串只包含非负整数，算符+、-、*、， ,左括号(和右括号)。整数除法需要向下截断。
你可以假定给定的表达式总是有效的。所有的中间结果的范围均满足[-231，231-1]。
注意:你不能使用任何将字符串作为表达式求值的内置函数，比如eval（ ) .
示例1:
输入:s = “1+1”
输出:2
示例2:
输入:s = “6-4/2”
输出:4
示例3:
输入:s =“2*(5+5*2)/3+(6/2+8)"
输出:21
提示:
- 1 <= s <= 104
- s 由整数、‘+’、‘-’、‘*’、’ / ‘、’(和’)′组成
- s是一个有效的表达式
// 含有嵌套的表达式求值
// 测试链接 : https://leetcode.cn/problems/basic-calculator-iii/
思路：f(i)代表：i这段的计算结果
嵌套条件：有括号
退出条件：遇到右括号
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;
}
}code2 394. 字符串解码
// 含有嵌套的字符串解码
// 测试链接 : https://leetcode.cn/problems/decode-string/
嵌套条件：有数字
退出条件：遇到右括号
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();
}
}code3 726. 原子的数量
// 含有嵌套的分子式求原子数量
// 测试链接 : https://leetcode.cn/problems/number-of-atoms/
思路：遇到大写和(意味着要结算历史，历史数据包含name或map以及cnt
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);
}
}
}
}
}