刷题记录-猿辅导2020

#include <iostream>
#include <vector>
#include <stack>

/*
5
A11B
(AA)2A
((A2B)2)2G
(YUANFUDAO)2JIAYOU
A2BC4D2
*/

using namespace std;

int getCount(const string &str, int loc, int &count) {
    int size = 0;
    while (loc < str.size()) {
        if (str[loc] >= '0' && str[loc] <= '9') {
            ++loc;
            ++size;
        } else break;
    }

    string tmp = str.substr(loc - size, size);
    count = stoi(tmp);
    return size;
}

string getStr(stack<char> &s) {
    stack<char> tmpS;

    while (!s.empty()) {
        if (s.top() != '(') {
            tmpS.push(s.top());
            s.pop();
        } else {
            s.pop();
            break;
        }
    }

    string tmp;
    while (!tmpS.empty()) {
        tmp += tmpS.top();
        tmpS.pop();
    }

    return tmp;
}

string unzipStr(const string &zipStr) {
    string ret;
    if (zipStr.empty()) {
        return ret;
    }

    stack<char> stack;

    for (int i = 0; i < zipStr.length(); ++i) {
        if (zipStr[i] != ')') {
            if (zipStr[i] >= '0' && zipStr[i] <= '9') {
                // 数字
                int count = 0;
                int move = getCount(zipStr, i, count);
                i += move - 1;

                string tmp;
                if (!stack.empty()) {
                    tmp += stack.top();
                    stack.pop();
                }

                for (int j = 0; j < count; ++j) {
                    for (auto &k:tmp) {
                        stack.push(k);
                    }
                }
            } else {
                stack.push(zipStr[i]);
            }
        } else {
            // 获取数字
            int count = 0;
            int move = getCount(zipStr, i + 1, count);

            // 获取串
            string str = getStr(stack);

            i += move;

            // 解压串压栈
            for (int j = 0; j < count; ++j) {
                for (char &k : str) {
                    stack.push(k);
                }
            }
        }
    }

    int size = stack.size();
    vector<char> vStr(size);

    for (int i = size - 1; i >= 0; --i) {
        vStr[i] = stack.top();
        stack.pop();
    }

    for (char i : vStr) {
        ret += i;
    }

    return ret;
}

int main() {
    int count;
    cin >> count;
    vector<string> data(count);
    for (int i = 0; i < count; ++i) {
        cin >> data[i];
    }

    for (int i = 0; i < count; ++i) {
        cout << unzipStr(data[i]) << endl;
    }

//    for (auto &d:data) {
//        cout << d << endl;
//    }
    return 0;
}