【LeetCode热题100】394. 字符串解码（栈）
一.题目要求
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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 <= 30
s 由小写英文字母、数字和方括号 ‘[]’ 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300]
四.解题思路
维护一个数字栈一个字母栈，遇到数字处理后存入数字栈，遇到字母或者左括号压入字母栈，遇到右括号弹出直到左括号的所有字母，并弹出这个左括号，然后弹出一个数字栈的数字进行计算，结果全部压回字母栈，以此类推。
五.代码实现
class Solution {
public:int toInt(string str) {int val = 0;int d = 1;for (string::iterator it = str.end() - 1; it > str.begin(); it--){val += d * (*it - '0');d *= 10;}val += d * (*str.begin() - '0');return val;}string decodeString(string s) {string tmp;stack<char> stk;stack<int> n;string num;string tmptotal;for (auto c : s){if (c >= '0' && c <= '9')num += c;else{if (num != ""){n.push(toInt(num));num = "";}if ((c >= 'a' && c <= 'z') || c == '['){stk.push(c);}else if (c == ']'){while (stk.top() != '['){tmp += stk.top();stk.pop();}stk.pop();int ci = n.top();n.pop();while (ci--){tmptotal += tmp;}for (int i = tmptotal.size() - 1; i >= 0; i--) stk.push(tmptotal[i]);tmp = "";tmptotal = "";}}}string ans1;while (!stk.empty()){ans1 += stk.top();stk.pop();}string ans2;for (int i = ans1.size() - 1; i >= 0; i--) ans2 += ans1[i];return ans2;}
};
六.题目总结
字符串的题典中典折磨