题目来源：leetcode394 字符串解码
题目描述：
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
解题思路：
方法一：递归
遍历字符串：
decode(string s,int &i)，i从0开始
1、当字符为数字时，计算连续数字，保存重复次数num
2、当为普通字符时候，ans直接加上字符
3、当为右边括号时候，跳过括号递归开始，t=decode(s,++i),t重复num次加入结果字符串ans中，num重置为0
4、当为左边括号的时候，跳出
class Solution {
public:
string decode(string s,int &i){
int num=0;
string ans="";
while(i<s.size()&&s[i]!=']'){
if(s[i]>='0'&&s[i]<='9') {
num=num*10+s[i]-'0';
}
else if(s[i]=='[')
{
string t=decode(s,++i);
while(num--)
ans+=t;
num=0;
}
else if(s[i]==']') break;
else ans+=s[i];
i++;
}
return ans;
}
string decodeString(string s) {
int i=0;
return decode(s,i);
}
};
方法二：
借助栈,一个栈保存数字，一个栈保存字符串。
遍历字符串。
1、若字符是数字，解析数字（可能存在连续），存入num
2、若字符是字母，则存入str中
3、若字符是左括号'[',把得到的字母和数字分别压栈，重设num=0,str=""
4、若字符是右括号']'，数字栈顶n出栈，作为重复次数，字符栈顶tmp出栈，作为拼接str的前缀字符串，一共拼接n次，即(tmp+=str)重复n次，拼接后的字符串再给str保存，即str=tmp。最终返回str,就是拼接好的字符串。
class Solution {
public:
string decodeString(string s) {
stack<int> nums;
stack<string> strs;
int i=0,num=0;
string str="";
for(i=0;i<s.size();i++){
if(s[i]>='0'&&s[i]<='9'){
num=num*10+s[i]-'0';
}
else if(s[i]=='['){
nums.push(num);
strs.push(str);
num=0;
str="";
}
else if(s[i]==']'){
int n=nums.top();
nums.pop();
string tmp=strs.top();
strs.pop();
while(n--)
tmp+=str;
str=tmp;
}
else str+=s[i];
}
return str;
}
};