题目：

给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

<br>

示例 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]

分析：

本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应，剩下的其实就是模拟了。 算法流程： 遍历字符串s，对于每个字符c：

  • 如果栈为空并且不是数字，说明此时是不用解码的字符，直接放入答案；
  • 否则，如果碰到数字，说明要开始解码，放入栈，并标记后面的字符都要放入栈，pushFlag设置为true，直到栈为空；
  • 否则，如果碰到 ']' 说明出现一对[]，需要解码：
    • 从栈中恢复需要重复num次的字符串，注意栈中弹出的为逆序，需要反转
    • 从栈中恢复数字，注意数字范围为[1, 300] 会出现多位，需要循环弹出，直到为空或不为数字
    • 如果此时栈为空，说明到当前位置所有的 [] 都已经解码，直接放入答案ans中即可，例：3[a]
    • 否则，如果栈不为空，说明还有 [ 没有解码，此时需要我们将中间嵌套的[]再次放入栈中，例：3[a2[c]] 中，2[c]解码完需要放入栈中，变为3[acc]，等待解码外层

AC代码：

class Solution {
public:string decodeString(string s) {string ans = "";stack<char> st; // 只记录数组 [] 和括号内的字符bool pushFlag = false;for (char c : s) {// 如果栈为空并且不是数字，说明此时是不用解码的字符，直接放入答案if (st.empty() && !isdigit(c)) {ans += c;} else if (isdigit(c)) { // 如果碰到数字，说明要开始解码，放入栈，并标记后面的字符都要放入栈，直到栈为空pushFlag = true;st.push(c);} else if (c == ']') { // 如果碰到 ']' 说明出现一对[]，需要解码// 从栈中恢复需要重复num次的字符串string temp = "";while (!isdigit(st.top())) {if (st.top() != '[') {temp += st.top();}st.pop();} // 从栈中恢复数字，因为数字范围为[1, 300] 会出现多位int num = 0, cnt = 0;while (!st.empty() && isdigit(st.top())) {num += (st.top() - '0') * pow(10, cnt);st.pop();cnt++;}// 从栈中弹出的是逆序的reverse(temp.begin(), temp.end());// 如果此时栈为空，说明到当前位置所有的 [] 都已经解码，直接放入答案ans中即可，例：3[a]if (st.empty()) {pushFlag = false;while (num--) {ans += temp;}} else { // 如果栈不为空，说明还有 [ 没有解码，此时需要我们将中间嵌套的[]再次放入栈中，例：3[a2[c]] 中，2[c]解码完需要放入栈中，变为3[acc]，等待解码外层while (num--) {int len = temp.size();if (len > 1) {for (int i = 0; i < len; i++) {st.push(temp[i]);}} else {st.push(temp[0]);}}}} else if (pushFlag) {st.push(c);}}return ans;}
};