[C++知识库]394. 字符串解码 C++ （难理解） 2021-08-23

394. 字符串解码
     1、递归写法（掌握）

class Solution {

public:
    int stoi(string temp_k)
    {
        int res = 0;
        int size = temp_k.size();
        for (int i = 0; i < size; ++i)
        {
            res = res * 10 + (temp_k[i] - '0');//注意这个减 '0'
        }
        return res;
    }

    bool isnum(char ch)
    {
        return (ch >= '0' && ch <= '9');
    }

    void addstr(string& str, int k, string s)
    {
        for (int cur_pos = 0; cur_pos < k; ++cur_pos)
            str.append(s);
    }

    string decodeString(string s)
    {
        int cur_pos = 0;
        return myDecodeString(s, cur_pos);
    }
    
    string myDecodeString(string s, int& cur_pos) 
    {
        int size = s.size();
        string res_str;
      
        while (cur_pos < size)
        {
            // cout << "s[cur_pos]: " << s[cur_pos] << endl;
            if (isnum(s[cur_pos]))
            {
                int beg = cur_pos;
                while (cur_pos < size && s[cur_pos] != '[')
                {
                    // cout << "num:" << s[cur_pos] << endl;
                    cur_pos++;
                }
                string temp_k = s.substr(beg, cur_pos - beg);
                cur_pos++;
                string str = myDecodeString(s, cur_pos);
                addstr(res_str, stoi(temp_k), str);
                // cout << "add res_str: " << res_str << endl;
            }
           
            else if (s[cur_pos] == ']')  
            {
                cur_pos++;
                return res_str;
            }  
            else
            {
                res_str.push_back(s[cur_pos]);
                cur_pos++;
            }  
        }
        return res_str;
    }
};

2、栈辅助方法 数字栈与字母栈

class Solution {
public:
    string decodeString(string s)
    {
        string res;
        int multi = 0;
        stack<int> stack_multi;//数字栈
        stack<string> stack_res;
        for(char c : s) 
        {
            if(c >= '0' && c <= '9') 
                multi = multi * 10 + (c -'0');

            else if(c == '[') 
            {
                stack_multi.push(multi);
                stack_res.push(res);
                multi = 0;
                res = "";
            }
            else if(c == ']') 
            {
                string tmp;
                int cur_multi = stack_multi.top();
                stack_multi.pop();
                for(int i = 0; i < cur_multi; i++) 
                    tmp.append(res);
                res = stack_res.top() + tmp;
                stack_res.pop();
            }
            else 
                res.push_back(c);
        }
        return res;
    }
};