LeetCode刷题---栈---394

字符串解码

394. 字符串解码 - 力扣（LeetCode）

题目

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

编码规则为: 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:
    string decodeString(string s) {
        stack<char> s1;
        string result;
        for(auto i : s) {
            if((i>='a' && i<='z') || i == '[') {
                s1.push(i);
            } else if (i == ']') {
                vector<char> temp;
                while(s1.top() != '[') {
                    temp.push_back(s1.top());
                    s1.pop();
                }
                s1.pop();

                int sum = 0, mul = 1;
                while(!s1.empty() && (s1.top()>='0' && s1.top()<='9')) {
                    sum += (s1.top() - '0') * mul;
                    mul *= 10;
                    s1.pop();
                } 
                for(int j=0; j<sum; j++) {
                    for(int k=temp.size()-1; k>=0; k--) {
                        s1.push(temp[k]);
                    }
                }
                temp.clear();
            } else {
                s1.push(i);
            }
        }

        int sum = s1.size();
        for(int i=0; i<sum; i++) {
            result += s1.top();
            s1.pop(); 
        }
        reverse(result.begin(), result.end());
        return result;
    }
};