数据结构解答力扣394代码

LeetCode 394题要求将给定的字符串s进行解码，解码规则如下：

s被分成若干个子串，每个子串要么表示一个字符，要么表示重复的次数和一个子串，即一个形如[k|sub_s]的子串表示sub_s重复k次。

例如：字符串 "3[a]2[bc]" 可以表示为 "aaabcbc"。

解答思路：
该问题可以使用栈来解决，遍历字符串s，如果当前字符是数字，则继续遍历直到获取完整的数字；如果当前字符是左括号，将之前获取到的数字压入栈中，并将数字置零，将左括号压入栈中；如果当前字符是右括号，则弹出栈顶的元素，直到弹出的元素为左括号，然后再弹出栈顶的元素作为重复次数，重复栈顶的元素并将结果压入栈中。最终栈中只剩下一个元素即为解码结果。

代码如下：

class Solution {
public:
    string decodeString(string s) {
        stack<int> nums;
        stack<string> strs;
        string str = "";
        int num = 0;
        for (char c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                nums.push(num);
                num = 0;
                strs.push(str);
                str = "";
            } else if (c == ']') {
                int k = nums.top();
                nums.pop();
                for (int i = 0; i < k; i++) {
                    strs.top() += str;
                }
                str = strs.top();
                strs.pop();
            } else {
                str += c;
            }
        }
        return str;
    }
};