HDU 1274 展开字符串 （递归+string类）

题目链接：HDU 1274 展开字符串

中文题。

左括号进入DFS函数，右括号return到上一层。

注意return回去的是这个一层递归中的括号中的字母串。

AC代码：

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<string>

using namespace std;

char str[300];

bool vis[300];

int len;

string dfs(int pos)

{

	int i,k;

	int num=0;

	string ans="";

	string temp="",h="";

	for(i=pos;i<len;i++)

	{

		if(!vis[i])

		{

			vis[i]=true;

			if(str[i]>='0' && str[i]<='9')

			{

				num=num*10+str[i]-'0';

				continue;

			}

			if(str[i]>='a' && str[i]<='z')

			{

				if(num==0)

					num=1;

				for(k=0;k<num;k++)

					temp+=str[i];

				num=0;

			}

			if(str[i]=='(')

			{

				ans+=temp;

				h=dfs(i+1);

				if(num==0)

					num=1;

				for(k=0;k<num;k++)

					ans+=h;

				temp="";

				num=0;

			}

			if(str[i]==')')

			{

				ans+=temp;

				return ans;//这一层的括号中的字母返回到上一层

			}

		}

	}

	ans+=temp;

	return ans;

}

int main()

{

	int t,i,j;

	string out;

	while(scanf("%d",&t)!=EOF)

	{

		while(t--)

		{

			memset(vis,false,sizeof vis);

			scanf("%s",str);

			len=strlen(str);

			out=dfs(0);

			cout<<out<<endl;

		}

	}

	return 0;

}

/*

100

3(ab)

1(1a2b1(ab)1c)

3(ab2(4ab))

ababa

ab3(cd)2e

3((ab))

3(3(ab))

3(3(ab)2(cd))

1a1a

1b

*/