1867.txt

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

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;

#define YES 	{ printf( "same\n" ); 		continue; }
#define NO		{ printf( "different\n" );	continue; }
#define PT(a) 	(printf("a\n"));

struct node
{
	vector< node* > next;
	char c;

}mem[500];

char w[1000];
int u;

node* new_node()
{
	mem[u++].next.clear();
	return &mem[u-1];
} 

int creat( int a, node *p )
{
	node *q;
	p->c = w[a];
	a++;
	if( w[a] == '(' )
	{
		a++;
		while( 1 )//w[a] != '\0' )
		{
			if( w[a] == ',' ) a++;
		
			q = new_node();
			p -> next.push_back( q );
			q -> next.push_back( p );
			a = creat( a, q );

			if( w[a] == ')' )
			{
				a++;
				return a;
			}
		}
	}
	return a;
}

	
bool judge( node *p1, node *f1, node *p2, node *f2 )
{
	int d1 = p1->next.size(), d2 = p2->next.size(), i, j, k;

	if( d1 != d2 || p1->c != p2->c ) return false;	

	for( i = 0; i < d1; i++ )
		if( p1->next[i] == f1 ) break;

	for( j = 0; j < d2; j++ )
		if( p2->next[j] == f2 ) break;

	for( k = 1; k < d1; k++ )
		if( ! judge( p1->next[(i+k)%d1], p1, p2->next[(j+k)%d2], p2 ) )
			return false;

	return true;
}

int main()
{
	bool key;
	int cas, i, j, h;


	scanf( "%d", &cas );

	while( cas-- )
	{

		u=0;

		scanf( "%s", w );
		mem[u].next.clear();
		u++;
		creat( 0, &mem[u-1] );
		
		h = u;

		scanf( "%s", w );
		mem[u].next.clear();
		u++;
		creat( 0, &mem[u-1] );
		
		if( u == 2 ) 
		{
			if( mem[0].c == mem[1].c )	YES
			else NO
		}

		if( h*2 != u )
			NO

		for( i=0; i < h; i++ )
		if( mem[i].next.size() == 1 )
			break;

		if( i < h )
		{
			for( key=1, j=h; j < u && key ; j++ )
			if( mem[j].next.size() == 1 && mem[j].c == mem[i].c )
			{
				if( judge( mem[i].next[0], &mem[i], mem[j].next[0], &mem[j] ) )
				{
					key = 0;
				}
			}

			if( !key ) YES
		}
		
		NO
	}
	return 0;
}