题目

394. 字符串解码

思路

创建两个栈，一个栈存储数字，另一个栈存储字符串。如果当前的字符为数位，解析出一个数字并进栈，如果当前的字符为字母或者左括号，直接进栈，如果当前的字符为右括号，开始出栈，一直到左括号出栈，出栈序列反转后拼接成一个字符串，此时取出栈顶的数字，根据这个次数和字符串构造出新的字符串，重复如上操作，最终将栈中的元素按照从栈底到栈顶的顺序拼接起来。

代码

class Solution {
public:string decodeString(string s){stack<int> nums; // 用于存储数字stack<string> st; // 用于存储字符串string tmp; // 临时字符串int num = 0; // 当前数字int n = s.size(); // 字符串长度for (int i = 0; i < n; i++) {if (isdigit(s[i])) {num = 10 * num + s[i] - '0'; // 解析数字} else if (isalpha(s[i])) {tmp.push_back(s[i]); // 解析字母} else if (s[i] == '[') {nums.push(num); // 数字入栈num = 0; // 重置数字st.push(tmp); // 字符串入栈tmp.clear(); // 清空临时字符串} else if (s[i] == ']') {int cnt = nums.top(); // 获取栈顶数字nums.pop(); // 数字出栈string str = tmp; // 临时字符串for (int j = 0; j < cnt; j++) {st.top() += str; // 重复字符串}tmp = st.top(); // 更新临时字符串st.pop(); // 字符串出栈}}return tmp; // 返回解码后的字符串}
};