给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为:?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]??
class Solution {
public:
? ?bool isdight(string c)
{
? ? string s = "0123456789";
? ? if (s.find(c) != -1)
? ? {
? ? ? ? return true;
? ? }
? ? return false;
}
int strToNum(string str)
{
? ? int wei = 1;
? ? int num = 0;
? ? int size = str.size();
? ? int cur = size - 1;
? ? int ret = 0;
? ? while (cur >= 0)
? ? {
? ? ? ? int a = (str[cur] - '0');
? ? ? ? ret = ret + a*wei;
? ? ? ? wei = wei * 10;
? ? ? ? cur--;
? ? }
? ? return ret;
}
string decodeString(string s) {
? ? string ret = "";
? ? stack<string>stk;
? ? int cur = 0;
? ? int len = s.size();
? ? int num = 0;
? ? while (cur<len)
? ? {
? ? ? ? if (s[cur] == ']')
? ? ? ? {
? ? ? ? ? ? num--;
? ? ? ? ? ? string tmp = "";
? ? ? ? ? ? while (!stk.empty())
? ? ? ? ? ? {
? ? ? ? ? ? ? ? string top = stk.top();
? ? ? ? ? ? ? ? stk.pop();
? ? ? ? ? ? ? ? if (top == "[")
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? tmp = top + tmp;
? ? ? ? ? ? }
? ? ? ? ? ? string numStr = "";
? ? ? ? ? ? while (!stk.empty())
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (stk.top().size()>1)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (!isdight(stk.top()))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? string top = stk.top();
? ? ? ? ? ? ? ? stk.pop();
? ? ? ? ? ? ? ? numStr = top + numStr;
? ? ? ? ? ? }
? ? ? ? ? ? int numrepeat = strToNum(numStr);
? ? ? ? ? ? string repeatStr = "";
? ? ? ? ? ? while (numrepeat>0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? repeatStr = repeatStr + tmp;
? ? ? ? ? ? ? ? numrepeat--;
? ? ? ? ? ? }
? ? ? ? ? ? if (num>0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? stk.push(repeatStr);
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? string tmp2 = "";
? ? ? ? ? ? ? ? while (!stk.empty())
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? tmp2 = stk.top()+ tmp2;
? ? ? ? ? ? ? ? ? ? stk.pop();
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ret = ret + tmp2 + repeatStr;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? if (s[cur] == '[')
? ? ? ? ? ? {
? ? ? ? ? ? ? ? num++;
? ? ? ? ? ? }
? ? ? ? ? ? stk.push(s.substr(cur,1));
? ? ? ? }
? ? ? ? cur++;
? ? }
? ? string remain = "";
? ? while (!stk.empty())
? ? {
? ? ? ? remain = stk.top()+ remain;
? ? ? ? stk.pop();
? ? }
? ? ret += remain;
? ? return ret;
}
};