腾讯刷题 压缩算法

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

输入描述:

输入第一行包含一个字符串s，代表压缩后的字符串。

S的长度<=1000;

S仅包含大写字母、[、]、|;

解压后的字符串长度不超过100000;

压缩递归层数不超过10层;

输出描述:

输出一个字符串，代表解压后的字符串。

输入例子1:

HG[3|B[2|CA]]F

输出例子1:

HGBCACABCACABCACAF

例子说明1:

HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF

这道题可以使用 递归 的算法来处理，当遇到第一个 [ 时，记录下后面的数组，然后将 | 后面的进行判断，若只有字母，可以进行解压，如果再次出现了 [ 那么就要现在处理当前所面临的压缩字符，以此往复，代码实现如下：

#include <iostream>

using namespace std;

string str, new_str;//定义写入字符串和输出字符串
int p;//指针

bool IS_letter(char ch)//判断是否为字母，在这里只有大写字母
{
    if(ch>='A' && ch<='Z')
    {
        return true;
    }
    return false;
}

int get_num()//对出现的数字字符进行数字化整合
{
    int num = 0;
    while(str[p]>='0' && str[p]<='9')
    {
        num *= 10;
        num += str[p] - '0';
        p++;
    }
    return num;
}

string get_str()
{
    string temp = "";//定义原字符串
    string new_temp = "";//定义解压后的字符串
    int num = get_num();//需要解压次数
    p++;//注意还有|
    while(str[p] != ']')
    {
        if(IS_letter(str[p]))
        {
            temp += str[p];
            p++;
        }
        if(str[p] == '[')
        {
            p++;
            temp += get_str();//递归调用
        }
    }
    p++;//去除]
    for(int i=0;i<num;i++)
    {
        new_temp += temp;
    }

    return new_temp;
}


int main()
{
    cin>>str;
    p = 0;
    new_str = "";
    for(;p<str.size();)
    {
        if(IS_letter(str[p]))//开头为字母的话，直接进入输出序列，一定不会解压
        {
            new_str += str[p];
            p++;
        }
        if(str[p] == '[')//出现了[时，进行解压
        {
            p++;
            new_str += get_str();
        }
    }
    cout<<new_str<<endl;
    return 0;
}