字符串解码（辅助栈法递归法)

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

s = "3[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

方案一：

1、辅助栈法，建立两个栈，一个存数字，一个存string，依次判断每个字符

string decodeString(string s) { string res = ""; stack <int> nums; stack <string> strs; int num = 0; int len = s.size(); for(int i = 0; i < len; ++ i) { if(s[i] >= '0' && s[i] <= '9') { num = num * 10 + s[i] - '0'; } else if((s[i] >= 'a' && s[i] <= 'z') ||(s[i] >= 'A' && s[i] <= 'Z')) { res = res + s[i]; } else if(s[i] == '[') //将‘[’前的数字压入nums栈内， 字母字符串压入strs栈内 { nums.push(num); num = 0; strs.push(res); res = ""; } else //遇到‘]’时，操作与之相配的‘[’之间的字符，使用分配律 { int times = nums.top(); nums.pop(); for(int j = 0; j < times; ++ j) strs.top() += res; res = strs.top(); //之后若还是字母，就会直接加到res之后，因为它们是同一级的运算 //若是左括号，res会被压入strs栈，作为上一层的运算 strs.pop(); } } return res; }

2、

总体思路与辅助栈法一致，不同点在于将 [ 和 ] 分别作为递归的开启与终止条件：

1.将源字符串逐字符压栈，直到遇见‘]’说明已经出现了一个需要解码的字段 2.弹栈找到‘[’记录[]之间的字符串，弹出来的是逆序，需要反转 3.解析k值，然后根据解码规则创建一个k次重复的字符串 4.将新字符串替换源字符串需要解码的部分，得到解码一次的字符串 5.将解码一次的字符串作为源字符串递归

string decodeString(string s) { string ret; stack<char> mystack; if (s.find('[') < s.size()) { for (char mem : s) {//将第一个需要解码的关键字压栈，即第一个以‘]’结束的字段 if (mem != ']') { mystack.push(mem); continue; } else break; } string substr_tmp; while (mystack.top() != '[') {//取出第一个需要解码的关键字，然后根据k值解码 substr_tmp.push_back(mystack.top()); mystack.pop(); } reverse(substr_tmp.begin(), substr_tmp.end()); mystack.pop(); int i = 0; int key = 0; while ((mystack.top() - '0') >= 0 && (mystack.top() - '0') < 10) { key += pow(10, i)*(mystack.top() - '0'); mystack.pop(); i++; if (mystack.empty()) break; } string substr_replace; while (key > 0) { substr_replace.append(substr_tmp); key--; } //完成第一个关键字的解码，然后替换源字符串中的内容 int pos = s.find(']') - substr_tmp.size() - 1 - i; s.erase(pos, substr_tmp.size() + 2 + i); s.insert(pos, substr_replace); ret = decodeString(s);//递归 return ret; } ret = s; return ret; }