力扣396

模拟栈，没有存‘[’,无法通过下面这个测试用例，遂放弃。

#include <string> #include <stack> #include <iostream> using namespace std; class Solution { public: //将字符操作后再压入栈 string decodeString(string s) { stack<string> str; stack<int> num; string currStr = ""; string lastStr = ""; int n = 0; string res = ""; for(int i = 0;i < s.size();){ if(s[i] <= 'z' && s[i] >= 'a') { while(i < s.size() && s[i] <= 'z' && s[i] >= 'a'){ currStr.push_back(s[i]); i++; } str.push(currStr); currStr.clear(); } else if(s[i] >= '0' && s[i] <= '9'){ while(i < s.size() && s[i] >= '0' && s[i] <= '9'){ n = n*10 + s[i] - '0'; i++; } num.push(n); n = 0; } else if(s[i] == ']'){ int count = num.top(); num.pop(); string curr = ""; while(count--){ curr = curr + str.top(); } str.pop(); if(!str.empty()){ lastStr = str.top() + curr; str.pop(); } else{ lastStr = curr; } str.push(lastStr); i++; } else{ i++; } } //将字母栈还原 while(!str.empty()){ res = str.top() + res; str.pop(); } return res; } }; int main(){ Solution s; string str = "3[z]2[2[y]pq4[2[jk]e1[f]]]ef"; cout << s.decodeString(str) << endl; return 0; }

新写法，完全模拟，注意，最后要反转。

#include <string> #include <stack> #include <iostream> #include <algorithm> using namespace std; class Solution { public: //将字符操作后再压入栈 //‘[’压栈不能省 string decodeString(string s) { stack<char> str; stack<int> num; int n = 0; for(int i = 0;i < s.size();i++){ if(s[i] <= '9' && s[i] >= '0'){ n = n * 10 + s[i] - '0'; } else if(s[i] >= 'a' && s[i] <= 'z'){ str.push(s[i]); } else if(s[i] == '['){ num.push(n); n = 0; str.push('['); } else if(s[i] == ']'){ string curr = ""; while(str.top() != '['){ curr = str.top() + curr; str.pop(); } str.pop(); int currN = num.top(); num.pop(); while(currN--){ for(int i = 0;i < curr.size();i++){ str.push(curr[i]); } } } } string res = ""; while(!str.empty()){ res.push_back(str.top()); str.pop(); } reverse(res.begin(),res.end()); return res; }; }; int main(){ Solution s; string str = "3[z]2[2[y]pq4[2[jk]e1[f]]]ef"; cout << s.decodeString(str) << endl; return 0; }