字符串解码：给一个字符串，返回解码后的字符串。
题目
字符串解码，给一个字符串s，返回解码后的字符串。字符串编码规则为k[str]表示括号内部str字符串正好重复k次，k保证为整数，并且输入的字符串肯定符合这种编码规则不会有额外的空格。
注意事项：
- 注意括号可能发生嵌套，例如输入字符串为
3[a2[c]]应该返回accaccacc - 1 <= s.length <= 30
- s由小写英文字母、数字和方括号'[]' 组成
- s保证是一个有效的输入。左括号前肯定指明了重复次数，对于不重复的字符串不会用括号将它括住。
- s中所有整数的取值范围为[1, 300]
输入输出
| 输入 | 输出 |
|---|---|
| 3[a]2[bc] | aaabcbc |
| abc3[d2[e]] | abcdeedeedee |
初步分析
因为嵌套括号的可能性，所以这道题需要使用数据结构栈，一个栈保存数字代表重复的次数，一个栈保存当前需要重复拼接的字符串。
我的思路
使用List集合存储每个数字，然后没有考虑到临时字符串的存储。没有理解到这道题的核心思想：当发生嵌套括号时，需要从最内层的元素向外拼接。从内向外。
题解思路
countStack栈存储需要重复的次数，stringStack栈存储当前的临时字符串。- 创建StringBuilder对象curStr为当前拼接的字符串，用于应对连续字符的情况，例如
2[abc] - 创建整形count记录每个重复次数，例如
2[a3[b]]则压栈顺序为：2--->3 - 将目标字符串转为char数组进行遍历，依次判断每个字符情况。
- 最终curStr是拼接完成的，解密后的字符串，返回。
关键点
第四步，遇到特定字符该做什么？
我们先假设最理想情况：e10[a]3[b]abc
//首先判断字符是数字的情况
if(Character.isDigit(ch)){
//将字符转为对应的10进制数字,因为重复次数范围在1~300
int count = 0;
count = count * 10 + ch - '0';
//但这里不能判断是否应该将count压栈，因为无法确定ch后面是否还有数字
}
//2.判断ch = '['情况
if(ch == '['){
//匹配到左括号，肯定代表count已经固定得到了，将其压栈
countStack.push(count);
//因为第一个左括号前可能有未在括号内的字符串，也就是重复次数为1的字符串，所以需要将当前字符串压栈
stringStack.push(curStr);
//当前字符串已记录，让其恢复为空字符串
curStr = new StringBuilder();
//count也需要还原
count = 0;
}
//3.判断ch是字母的情况
if(Character.isLetter(ch)){
curStr.append(ch);
}
//4.判断ch = ']'右括号
if(ch == ']'){
//每当匹配到右括号，算是一个终结条件，无论多少个括号嵌套，当匹配到右括号时后面一定都是右括号直到结束
/*当前栈、curStr、count的情况
countStack [10]
stringStack ["e"]
curStr "a"
count 0
*/
//观察本次输入范例，我们需要在e后面拼接10个a字符
count = countStack.pop();
StringBuilder temp = new StringBuilder(stringStack.pop());
for(int i=0;i<count;i++){
temp.append(curStr);
}
curStr = temp;
count = 0;
}
根据上面代码我们再分析这种情况a2[b3[c]]结果应该为abcccbccc
//第一次匹配到]
/*
countStack [2,3] 栈顶为3
stringStack ["a","b"] 栈顶为"b"
curStr "c"
count 0
*/
//第二次匹配到]
/*
countStack [2] 栈顶为2
stringStack ["a"] 栈顶为"a"
curStr "bccc"
count 0
*/
//第二次执行完后
curStr = "abcccbccc"
图解
代码
public class DecodeStr {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
System.out.println(getResult(str));
}
private static String getResult(String s) {
Stack<Integer> countStack = new Stack<>();
Stack<String> stringStack = new Stack<>();
//最终返回的就是他
StringBuilder curStr = new StringBuilder();
int count = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)){
count = count * 10 + (c - '0');
}else if (c == '['){
countStack.push(count);
stringStack.push(curStr.toString());
curStr = new StringBuilder();
count = 0;
}else if (c == ']'){
//找到了最内部的字符串，从stringStack中弹出
StringBuilder decodedString = new StringBuilder(stringStack.pop());
//寻找该字符串重复次数
int repeatCount = countStack.pop();
for (int i = 0; i < repeatCount; i++) {
decodedString.append(curStr);
}
curStr = decodedString;
}else {
curStr.append(c);
}
}
return curStr.toString();
}
}