字符串解码：给一个字符串，返回解码后的字符串。

题目

字符串解码，给一个字符串s，返回解码后的字符串。字符串编码规则为k[str]表示括号内部str字符串正好重复k次，k保证为整数，并且输入的字符串肯定符合这种编码规则不会有额外的空格。
注意事项：

• 注意括号可能发生嵌套，例如输入字符串为3[a2[c]]应该返回accaccacc
• 1 <= s.length <= 30
• s由小写英文字母、数字和方括号'[]' 组成
• s保证是一个有效的输入。左括号前肯定指明了重复次数，对于不重复的字符串不会用括号将它括住。
• s中所有整数的取值范围为[1, 300]

输入输出

初步分析

因为嵌套括号的可能性，所以这道题需要使用数据结构栈，一个栈保存数字代表重复的次数，一个栈保存当前需要重复拼接的字符串。

我的思路

使用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();
    }
}