71、栈-字符串解码

 思路：

3[a]==>aaa

3[a2[c]]===>3[a cc]===>acc acc acc

由上面两个例子可以看出，当遇到[的时候可以先不结算，当遇到 ]的时候结算，结算左侧最近的右括号[。然后继续遍历。这个也是使用栈的思想。可以使用两个栈一个用于存储字符的栈 (strStack) 和一个用于存储重复次数的栈 (numStack)。

代码如下：

class Solution {
    public static String decodeString(String s) {
        if (s == null || s.isEmpty()) {
            return ""; // 如果输入为空，则直接返回空字符串
        }
        Stack<StringBuilder> strStack = new Stack<>(); // 用于存储字符串状态的栈
        Stack<Integer> numStack = new Stack<>(); // 用于存储重复次数的栈
        int k = 0; // 用于构建当前读取到的数字，即重复次数
        StringBuilder cur = new StringBuilder(); // 当前操作的StringBuilder

        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                k = k * 10 + (ch - '0'); // 处理数字，构建完整的重复次数
            } else if (ch == '[') {
                numStack.push(k); // 将当前重复次数压入栈
                strStack.push(new StringBuilder(cur)); // 将当前字符串压入栈
                k = 0; // 重置重复次数
                cur = new StringBuilder(); // 重置当前字符串
            } else if (ch == ']') {
                StringBuilder temp = cur; // 保存当前构建的字符串
                cur = strStack.pop(); // 从栈中弹出前一个字符串状态
                for (int i = numStack.pop(); i > 0; i--) { // 根据次数重复添加字符串
                    cur.append(temp);
                }
            } else {
                cur.append(ch); // 直接向StringBuilder追加非特殊字符
            }
        }
        return cur.toString(); // 将最终的StringBuilder转为字符串并返回
    }
}