腾讯2020校招第一次笔试第1题

    小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q
发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字
符串S将会压缩为[m|S](m为一个整数且1<=m<=100)，例如字符串ABCABCABC将会被压
缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？ 

输入描述:
输入第一行包含一个字符串s，代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

输出描述:
输出一个字符串，代表解压后的字符串。
示例1
输入
HG[3|B[2|CA]]F
输出
HGBCACABCACABCACAF
说明
HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF

这个题，是比较容易想到用栈来处理的，因为涉及到括号[]内的内容先处理，这是很显然应该用栈的。而想要把[]这一段内容写成一般的字符串，也是不难的。这道题最难处理的地方在于，[]这一段字符串写成一般形式以后，怎么保存下来。如果想要存到原来的字符串，因为[]写成一般形式后，长度可能发生变化，因此需要移动原来的字符串，这是很不方便的；而如果保存到一个新的字符串里面，就会出现一个问题：这段新的字符串，可能又在另一对[]里面，这个时候需要看原来的字符串和新的字符串，这也是很难操作的。

当时写这道题的时候，这两种办法都想到了，但是都无法实现，后来看了别人的解法，是把原来的字符串一个一个字符地存到栈里面，等遇到’]‘的时候，就把字符从栈中一个一个拿出来直到遇到’[’，然后就开始把这一段[]的内容写成一般形式（正如前面所说，这是很容易想到的）。关键是，写成一般形式以后，再度写回栈里（这是没那么容易想到的）。实现的代码如下：

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main()
{
    string str;
    while (cin >> str)
    {
        stack <char> sta;
        string ans;
        for (int i = 0; i < str.size(); ++i)
        {
            if (str[i] != ']')
            {
                sta.push(str[i]);    //没遇到']'，就要把字符压入栈
            }
            else
            {
                char tmp_c = sta.top();
                string tmp_s;
                while (tmp_c >= 'A' && tmp_c <= 'Z')    
                	//把[m|S]中的S提取到tmp_s
                {
                    tmp_s = tmp_c + tmp_s;
                    sta.pop();
                    tmp_c = sta.top();
                }
                
                if (!sta.empty())    //去掉'|'
                {
                    sta.pop();
                    tmp_c = sta.top();
                }
                
                int n = 0, cnt = 1;    
                while (tmp_c >= '0' && tmp_c <= '9')    
                	//把[m|S]中的m提取到n，cnt为位数（因为m可能不止个位）
                {
                    n += (tmp_c - '0') * cnt;
                    cnt *= 10;
                    sta.pop();
                    tmp_c = sta.top();
                }
                
                if (!sta.empty())    //去掉'['
                {
                    sta.pop();
                }
                
                while (n--)    //把tmp_s压入栈n次
                {
                    for (auto it : tmp_s)
                    {
                        sta.push(it);
                    }
                }
                
            }
        }
        while (!sta.empty())
        {
            ans = sta.top() + ans;
            sta.pop();
        }
        cout << ans << endl;
    }
    return 0;
}

更多精彩内容，敬请期待。

2020.2.27