本文共 1087 字，大约阅读时间需要 3 分钟。

>Description

一个字符串S，S是已经被加密过的字符串。现在要求把字符串S还原。字符串S可能会出现这样的格式：k(q)，它表示字符串q重复了k次，其中q是0个或多个字符，而k是一个数字，范围是0至9。你只要把k(q)这样的格式全部展开，就能把S还原了，你要输出还原后的字符串的长度。

---

>Input

一行，一个字符串S。字符串S只由‘（’、‘）’、0至9的数字组成，长度不超过50。所有的括号都是能匹配的，不用判断。

>Output

一个整数，还原后的字符串的长度。答案不会超过2147483647。

---

>Sample Input

33(562(71(9)))

>Sample Output

19

---

>解题思路

递归算法：遇到一个括号，就把对应括号里面的内容递归，返回值为字符串长度。

如果当前字符不为括号，也不为括号前面的k，就直接在字符串长度上累加；

如果为括号，就找到对应右括号递推，字符串长度累加上k*返回的长度；

---

>代码

#include
   
    #include
    
     #include
     
      using namespace std;string s;int lil(int l,int r) //l,r分别为起始位置，终止位置{
   	int sum=0,t=0,cyz;	while(l<=r)	{
   		if(s[l]=='(')		{
   			cyz=1;			for(int i=l+1;i<=r;i++) //找对应的右括号			{
   				if(s[i]=='(') cyz++; //遇到左括号说明要找的右括号要++				if(s[i]==')') cyz--; //遇到右括号就--				if(cyz==0) //如果括号找到(完)了				{
   					sum+=t*lil(l+1,i-1); //递归，累加上数值			 	    l=i; t=0; //从右括号后面开始			 	    break;				}			}		}		else if(s[l+1]=='(') t=s[l]-'0'; //如果为k的话要记录下来		else sum++; //否则直接累加		l++; //下一个字符	}	return sum;}int main(){
   //	freopen("b.in","r",stdin);//	freopen("b.out","w",stdout);	cin>>s;	printf("%d",lil(0,s.size()-1));	return 0;}
     
    
   

转载地址：http://nkggn.baihongyu.com/