给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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"提示：
1 <= s.length <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入。s中所有整数的取值范围为[1, 300]
解题思路：栈
这道题因为在遍历途中，有可能出现嵌套的情况，所以我们需要知道当前括号前面的嵌套情况，就可以利用栈的 “先进后出” 特性来解决问题，对于这道题，我们可以使用两个栈，一个存放数字，一个存放前面已经保存的字符串！
其实这道题难在情况比较多，我们只要对每种情况进行讨论，就能解决这道题！下面给出这道题遇到的几个情况：
- 遇到数字：
- 将字符数字转化为整型之后，直接入数字栈即可。（注意有可能是多位数，要提取完整的数字）
- 遇到
[：- 说明此时后面的字符串是一个需要解码的部分，所以将方括号后面的字符串拎出来放入字符串栈。
- 遇到
]：- 将数字栈和字符串栈的栈顶元素都出栈，然后重复
k次后将新字符串尾插到字符串栈的栈顶字符串尾部。因为有可能此时遇到的]号是一个嵌套的字符串解码部分，所以我们需要将其尾插到前一个保存着的字符串尾部，作为一个新整体！
- 将数字栈和字符串栈的栈顶元素都出栈，然后重复
- 遇到的是字符：
- 说明此时前面已经没有
[号了，因为对于不是单独的字符串，已经放在第二种情况中解决了！因此是单独的字符串，所以将该字符串提取出来然后尾插到字符串栈的栈顶字符串后面即可。
- 说明此时前面已经没有
栈顶元素就是最后的结果！要注意的就是在不断的移动 i 的时候，要注意何时需要进行 i++，下面结合代码去参考！
最后还有一个细节，就是字符串栈因为涉及到对栈顶元素尾插的操作，如果我们不想太麻烦去判断的话，可以直接向下面的代码一样，在初始化的时候先入栈一个空串，这样子就防止了循环时候出现的边界情况，省了很多事情！
class Solution {
public:
string decodeString(string s) {
stack<int> num_st;
stack<string> string_st;
string_st.push(""); // 放入一个空串，防止了循环时候出现的边界情况
int i = 0;
while(i < s.size())
{
if('0' <= s[i] && s[i] <= '9')
{
num_st.push(get_whole_num(s, i)); // 直接入数字栈
}
else if('a' <= s[i] && s[i] <= 'z')
{
string_st.top() += get_whole_string(s, i); // 将单独的字符串入栈
}
else if(s[i] == '[')
{
i++; // 记得是提取的是[后面的字符串，所以要先i++
string_st.push(get_whole_string(s, i));
}
else if(s[i] == ']')
{
int num = num_st.top();
num_st.pop();
string tmp = string_st.top();
string_st.pop();
while(num--)
string_st.top() += tmp;
i++; // 最后别忘了要i++跳过]
}
}
return string_st.top();
}
int get_whole_num(string& s, int& i)
{
int ret = 0;
while('0' <= s[i] && s[i] <= '9')
{
ret = ret*10 + (s[i] - '0');
i++;
}
return ret;
}
string get_whole_string(string& s, int& i)
{
string ret;
while(i < s.size() && 'a' <= s[i] && s[i] <= 'z') // 注意判断是否越界
{
ret += s[i];
i++;
}
return ret;
}
};