问题：给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例：

输入：s = "3[a]2[bc]"
输出："aaabcbc"输入：s = "3[a2[c]]"
输出："accaccacc"输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

思路：

• 栈 利用两个栈，一个用来存数字（数字栈），一个用来存数字之前的字符串（字符串栈）。

算法流程如下：

• 当c为数字时，将c转化为数字mul，入数字栈，以便后边将[]中的字符串按规则转化
• 当c为字符时，直接拼接在res后面
• 当c为’['时，将当前的数字以及当前的res分别入数字栈和字符串栈，然后将这两个变量清空。这里注意，数字可能不止一位。
• 当c为’]'时，此时的res记录了[]中的字符串，然后取出数字栈栈顶的倍数，将其拼接为一个新字符串，最后再取出字符串栈栈顶的字符串进行拼接。

直到遍历完给定的字符串

这里的res需要结合例子好好体会，

当碰到’[‘时，mul和res入栈后都清空了，一直到遇到’]'号，res表示的是中括号中的字符串

若当前字符c既不是数字，这个字符也不在[]中时，res表示 对当前字符以及其之前的所有字符组成的子字符串的 解码

class Solution {public String decodeString(String s) {StringBuilder res = new StringBuilder();int mul = 0;Deque<Integer> stackMul = new LinkedList();Deque<String> stackRes = new LinkedList();for(char c: s.toCharArray()){if(c == '['){stackMul.push(mul);stackRes.push(res.toString());mul = 0;res = new StringBuilder();} else if(c == ']'){StringBuilder temp = new StringBuilder();int cur_mul = stackMul.pop();//按倍数拼接字符串for(int i = 0; i < cur_mul; i++){temp.append(res);}//将拼接好的字符串与中括号前的字符串拼接在一起 res = new StringBuilder(stackRes.pop() + temp.toString());} else if(Character.isDigit(c)){//记录倍数mul = mul * 10 + (int) (c - '0');} else {res.append(c);}}return res.toString();}
}

整理思路，记录博客，以便复习。若有误，望指正~