ACM 122 Trees on the level
作法: /*認為測資深度不會超過 13*/
先建出關係圖 之後就分析字串跑樹 並記錄點
之後整個搜過一次(建表 因為階層走訪) 檢查是否有全部搜到 並做判斷
/************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int NUM[100000];
int link[100000][2]={0},ltop=0;
void MAKE(int now,int L)
{
if(L>13) return;
else
{
link[now][0]=++ltop;
MAKE(ltop,L+1);
link[now][1]=++ltop;
MAKE(ltop,L+1);
}
}
void Tree(int now,char s[],int L,int value)
{
if(s[L]=='\0') NUM[now]=value;
else
{
if(s[L]=='L') Tree(link[now][0],s,L+1,value);
else Tree(link[now][1],s,L+1,value);
}
}
void Scan(char s[])
{
int a,b,c,NUM=0,n=strlen(s);
for(a=1;a<n;a++)
if(s[a]==',') break;
else NUM=NUM*10+s[a]-48;
char LR[1000]={0};
for(a+=1,b=0;a<n-1;a++,b++)
LR[b]=s[a];
LR[b]='\0';
Tree(0,LR,0,NUM);
/* printf("%d %s %d\n",NUM,LR,b);*/
}
int FIND[100][100],Ftop[100]={0},Ftime=0;
void print(int now,int L)
{
if(NUM[now]!=0)
{
/* printf("%d %d\n",NUM[now],L);*/
FIND[L][Ftop[L]++]=NUM[now];
Ftime++;
if(NUM[link[now][0]]!=0) print(link[now][0],L+1);
if(NUM[link[now][1]]!=0) print(link[now][1],L+1);
}
}
main()
{
MAKE(0,0);
char s[5000];
int N,a,b;
while(scanf("%s",s)==1)
{
int time=1;
Scan(s);
Ftime=0;
while(scanf("%s",s)==1)
if(strlen(s)==2) break;
else
Scan(s),time++;
print(0,1);
if(Ftime==time)
{
for(a=1;a<100;a++)
for(b=0;b<Ftop[a];b++)
printf("%d ",FIND[a][b]);
printf("\n");
}
else printf("not complete\n");
for(a=0;a<100000;a++) NUM[a]=0;
for(a=0;a<100;a++) Ftop[a]=0;
}
return 0;
}