题目：小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
输出例子1:
HGBCACABCACABCACAF
例子说明1:
HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF
分析：
题目给出的为一串压缩过的字符串，压缩的规律为：将连续的重复字符字串压缩为一次，并记下出现的次数。现在要我们根据这个规律逆推出原字符串。这里我用了递归的方式来解这道题。
代码如下：
#include<stdio.h> #include<string.h> char s[1005]; //定义一个函数，输出重复的字符串 int decom(int i) { //确定重复次数 int sum = s[i]-'0'; while (1){ i++; if(s[i]=='|') break; else sum = sum*10 + s[i]-'0'; } //标记重复子串的起始位置 int flag = i+1; int j=0; i+=1; //遍历子串 for(j;j<sum;){ //有嵌套的话，递归 if(s[i] == '[') i = decom(i+1); //结束一次循环 else if(s[i] == ']'){ j++; i++; //printf("sum=%d i=%d j=%d flag=%d\n",sum,i,j,flag); if(j<sum){ i = flag; //printf("循环%d次\n",j); } } else{ printf("%c",s[i]); i++; } } //printf("return%d\n",i); return i; } int main() { scanf("%s",s); int i; for (i=0;i<strlen(s);i++) { if(s[i]=='[') //这里要注意减一 i = decom(i+1)-1; else if(s[i]==']' || s[i]=='|') continue; else printf("%c",s[i]); } return 0; }
