一、题目描述
二、算法原理
思路：使用双栈，一个栈原来存储字符串，另外一个存储整型数字；
1）一开始，把 string 栈先放个空字符串进去，方便后面操作；
2）如果碰到纯字母（非 [ 后面的字母），就让把这些字母提取出来拼接到 string 栈栈顶元素的后面：
3）如果遍历到数字，直接入 int 栈：
4）如果遍历到 ' [ '，就把 [ 后面的字母入 string 栈：
5）如果遍历到 ' ] '，就把双栈的栈顶元素拿出来，进行重复 K 次工作，重复结束之后把这个字符串拼接到栈顶元素的后面（这也是我为什么让 string 一开始放个空串进去的原因）：
最终答案：此时 string 的栈顶元素就是最终答案：
三、代码实现
class Solution { public: string decodeString(string s) { vector<int> int_stack; vector<string> char_stack(1,""); for(int i = 0; i < s.size();) { if(s[i] == '[')// "[" 后面跟字母 { i++; string str = ""; while(!isdigit(s[i]) && s[i] != ']' && s[i] != '[') { str += s[i]; i++; } char_stack.push_back(str); } else if(isdigit(s[i]))//纯数字 { int tmp = 0; while(isdigit(s[i])) { tmp = tmp * 10 + (s[i] - '0'); i++; } int_stack.push_back(tmp); } else if(s[i] != ']') { //纯字母 string str; while(i < s.size() && !isdigit(s[i]) && s[i] != ']' && s[i] != '[') { str += s[i]; i++; } char_stack.back() += str; } else // "]" { //']' //取双栈元素 int k = int_stack.back(); string str = char_stack.back(); //出双栈元素 int_stack.pop_back(); char_stack.pop_back(); string ret = ""; for(int j = 0; j < k; j++) ret += str; char_stack.back() += ret; i++; } } return char_stack.back(); } };
