class Solution { public: string decodeString(string s) { // pair 里存的是：<左括号前的倍数, 左括号前的字符串> stack<pair<int, string>> st; int time = 0; // 记录当前的倍数（注意初始化为 0） string result = ""; // 记录当前的字符串 for (int i = 0; i < s.size(); i++) { char c = s[i]; if (isdigit(c)) { // 处理多位数字" time = time * 10 + (c - '0'); } else if (isalpha(c)) { // 如果是字母，直接加到当前 result 里 result += c; } else if (c == '[') { // 遇到 '['，开始存档，并清空当前状态给括号内使用 st.emplace(time, result); time = 0; result = ""; } else if (c == ']') { // 遇到 ']'，提取存档 auto [last_time, last_string] = st.top(); st.pop(); // 将括号里的内容 (也就是现在的 result) 翻倍 string temp = ""; for (int k = 0; k < last_time; k++) { temp += result; } // 拼接到进括号前的历史字符串后面，成为新的 result result = last_string + temp; } } return result; } };time = time * 10 + (c - '0');
处理多位数字，例如"123"依次得到：1 → 12 → 123
输入："3[a2[c]]"
| 步骤 | 字符 | time | result | 栈 |
|---|---|---|---|---|
| 1 | '3' | 3 | "" | 空 |
| 2 | '[' | 0 | "" | [(3, "")] |
| 3 | 'a' | 0 | "a" | [(3, "")] |
| 4 | '2' | 2 | "a" | [(3, "")] |
| 5 | '[' | 0 | "" | [(3, ""), (2, "a")] |
| 6 | 'c' | 0 | "c" | [(3, ""), (2, "a")] |
| 7 | ']' | 0 | "a" + "c"×2 = "acc" | [(3, "")] |
| 8 | ']' | 0 | "" + "acc"×3 = "accaccacc" | 空 |
递归：
class Solution { public: string dfs(const string& s,int&index){ string res=""; while(index<s.size()&&s[index]!=']'){ if(!isdigit(s[index])){ res+=s[index++]; } else{ int num=0; while(index<s.size()&&isdigit(s[index++])){ num=num*10+s[index]-'0'; } //[ index++; string inner=dfs(s,index); index++; for (int i = 0; i < num; i++) { res += inner; } } } return res; } string decodeString(string s) { int index=0; return dfs(s,index ); }
