#include <iostream>
using namespace std;

struct tree
{
	char ch;
	tree *child[101];
	int len;
	tree *parent;
	int flag;
};

void InitTree(tree *&t);
void SetTree(tree *&t);
void PrintTree(tree *t);

int main()
{
	tree *t;
	while (1)
	{
		InitTree(t);
		SetTree(t);
		for (int i=1; i<=t->len; i++)
			PrintTree(t->child[i]);
		printf("\n");
	}
	return 0;
}

void InitTree(tree *&t)
{
	t=new tree;
	t->ch='#';
	t->len=0;
	int i;
	for (i=1; i<=100; i++)
		t->child[i]=NULL;
	t->parent=NULL;
	t->flag=0;
}


void SetTree(tree *&root)
{
	int i;
	char ct;
	scanf("%c",&ct);
	tree *p=root;
	if (ct=='(' || ct=='[')
	{
		p->len++;
		p->child[p->len]=new tree;
		p=p->child[p->len];
		p->ch=ct;
		p->len=0;
		for (i=1; i<=100; i++)	p->child[i]=NULL;
		p->parent=root;
		p->flag=0;
		SetTree(p);
	}
	else
	if (ct==')')
	{
		while (p->ch!='(' && p->ch!='#')
			p=p->parent;
		if (p->ch!='#')
		{
			p->flag=1;
			p=p->parent;
		}
		else
		{
			p=root;
			p->len++;
			p->child[p->len]=new tree;
			p=p->child[p->len];
			p->ch='(';
			p->len=0;
			for (i=1; i<=100; i++) p->child[i]=NULL;
			p->parent=root;
			p->flag=1;
			p=root;
		}
		SetTree(p);
	}
	else
	if (ct==']')
	{
		while (p->ch!='[' && p->ch!='#')
			p=p->parent;
		if (p->ch!='#')
		{
			p->flag=1;
			p=p->parent;
		}
		else
		{
			p=root;
			p->len++;
			p->child[p->len]=new tree;
			p=p->child[p->len];
			p->ch='[';
			p->len=0;
			for (i=1; i<=100; i++) p->child[i]=NULL;
			p->parent=root;
			p->flag=1;
			p=root;
		}
		SetTree(p);
	}
}


void PrintTree(tree *t)
{
	int i;
	if (!t) return ;
	printf("%c",t->ch);
	if (t->flag)
	{
		for (i=1; i<=t->len; i++)
			PrintTree(t->child[i]);
		if (t->ch=='(')	printf("%c",')');
		else	printf("%c",']');
	}
	else
	{
		if (t->ch=='(')	printf("%c",')');
		else	printf("%c",']');
		for (i=1; i<=t->len; i++)
			PrintTree(t->child[i]);
	}
}

• 别人都是dp...我用树...是我的错啊... (2243) lxj2006 2008-03-29 23:44:40
• 用dp过了还是不知道贪心错在哪里.... (2056) lxj2006 2008-04-01 21:26:05