1577.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//#define debug 1
#define NMAX 100
#define INF 1000000001
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
char str[NMAX][NMAX];
int n;
typedef struct a
{
	char w;
	int level;
	struct a *l,*r;
}btree;
btree *head;
void add(btree *&t,char w,int level)
{
	t=new btree;
	t->l=t->r=NULL;
	t->w=w;
	t->level=level;
}
int input()
{
	int i;
	for(i=0;;i++)
	{
		gets(str[i]);
		if(str[i][0]=='*')
		{
			n=i;
			return 0;
		}
		else if(str[i][0]=='$')
		{
			n=i;
			return 1;
		}
	}	
}
void make(btree *cp,char w,int level)
{
	if(cp->w>w)
		if(cp->l)
			make(cp->l,w,level);
		else
			add(cp->l,w,level);
	else
		if(cp->r)
			make(cp->r,w,level);
		else
			add(cp->r,w,level);
	
			
}
void tr(btree *cp)
{
	printf("%c",cp->w);
	if(cp->l)
		tr(cp->l);
	if(cp->r)
		tr(cp->r);
}
void solve()
{
	int i,j;
	add(head,str[n-1][0],1);
	int k=2;
	for(i=n-2;i>=0;i--)
	{
		for(j=0;j<strlen(str[i]);j++)
			make(head,str[i][j],k);
		k++;
	}
	tr(head);
	printf("\n");
}
	
main()
{
#if _DEBUG 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	while(1)
	{
		if(input())
		{
			solve();
			return 0;
		}
		else
		{
			solve();
		}
	}
#if _DEBUG 
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}