刷题记录-猿辅导2020

前言

今天在做猿辅导的题猿辅导2020校招笔试（一）, 说是挺难的. 这里a了笔试最后一道编程题, 写的有点乱, 记录下, 有空再来整理优化.

猿辅导APP需要下发一些宣传文本给学生，工程师们使用了一种字符压缩算法，为简单起见，假设被压缩的字符全部为大写字母序列，A,B,C,D....Z,压缩规则如下：
1.AAAB可以压缩为A3B (单字符压缩不加括号)
2.ABABA可以压缩为(AB)2A （多字符串压缩才加括号）

输入数据保证不会出现冗余括号，且表示重复的数字一定合法且大于1，即不会出现：
1.（A)2B ------- （应为：A2B）

2. ((AB))2C,-----(应为：（AB)2C )
3. （A)B ----- （应为：AB）
4. A1B，（AB)1C，（应为 AB，ABC）

注意：数字可能出现多位数即A11B或者(AB)10C或者A02这种情况。
A11B = AAAAAAAAAAAB
(AB)10C = ABABABABABABABABABABC
A02 = AA

数据分布：
对于60%的数据，括号不会出现嵌套，即不会有 ((AB)2C)2这种结构。
对于80%的数据，括号最多只嵌套一层，即不会有 (((AB)2C)2D)99 这种结构。
对于100%的数据，括号可以嵌套任意层。

#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;
}