1097.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
#include<string.h>
int in[100];
int graph[100][100];
int maxn;
char s[10000];
int findfirst(int t)
{
	while(s[t]!='(' && s[t]!=')')t++;
	if(s[t]==')')return -1;
	return t;
}
int findparter(int t)
{
	int c=0;
	while(1)
	{
		if(s[t]=='(')c++;
		else if(s[t]==')')c--;
		if(c==0)break;
		t++;
	}
	return t;
}
int cal(int i)
{
	int ret=0;
	while(s[i]<='9' && s[i]>='0')
	{
		ret=ret*10+int(s[i])-48;
		i++;
	}
	return ret;
}


int create(int f,int p)
{
	int d;
	d=cal(f+1);
	if(d>maxn)maxn=d;
	int son;
	while(1)
	{
		int ff=findfirst(f+1);
		if(ff==-1)break;
		int pp=findparter(ff);
		son=create(ff,pp);
		in[son]++;
		in[d]++;
		graph[son][d]=1;graph[d][son]=1;
		f=pp;
	}
	return d;
}


		




int main()
{
	int i,j,k;
	while(gets(s))
	{
		memset(in,0,sizeof(in));
	
		int f=findfirst(0);
		int p=findparter(f);maxn=0;	
		memset(graph,0,sizeof(graph));
		create(f,p);
		for(i=1;i<maxn;i++)
		{
			
			for(j=1;j<=maxn;j++)
			{
				if(in[j]==1)break;
			}
			if(i!=1)printf(" ");
			for(k=1;k<=maxn;k++)
			{
				if(graph[k][j]==1)break;
			}
			in[k]--;in[j]--;graph[k][j]=0;graph[j][k]=0;
			printf("%d",k);
		}
		printf("\n");





	}
	return 0;
}