#include <iostream.h>
#include <string.h>

#define M  9999999;
	char or[105];
	char r[105][105][300];
	int dp[105][105];
int min(int x,int y);

int main()
{
	int len,i,j,k,p,m,n,q;

	cin.getline(or,105);
	len=strlen(or);
	for (i=0;i<len;i++)
	{
		if(or[i]=='(')
		{
			r[i][i][0]='(';
			r[i][i][1]=')';
		}
		if(or[i]==')')
		{
			r[i][i][0]='(';
			r[i][i][1]=')';
		}
		if(or[i]=='[')
		{
			r[i][i][0]='[';
			r[i][i][1]=']';
		}
		if(or[i]==']')
		{
			r[i][i][0]='[';
			r[i][i][1]=']';
		}

	}
	for (i=0;i<len;i++)
		dp[i][i]=1;
	for (i=1;i<len;i++)
		dp[i][i-1]=0;	
	for (p=1;p<len;p++)
		for (i=0;i<len-p;i++)
		{
			j=i+p;
			if(j==len)continue;
			dp[i][j]=M;
			if(((or[i]=='(')&&(or[j]==')')) || ((or[i]=='[')&&(or[j]==']')))
			{
				if(dp[i][j]>dp[i+1][j-1])
				{
					dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
					if(or[i]=='(')
					{
						r[i][j][0]='(';
						for (k=0;;k++)
						{
							if(r[i+1][j-1][k]=='\0')break;
								r[i][j][k+1]=r[i+1][j-1][k];
						}
						r[i][j][k+1]=')';
					}
					if(or[i]=='[')
					{
						r[i][j][0]='[';
						for (k=0;;k++)
						{
							if(r[i+1][j-1][k]=='\0')break;
								r[i][j][k+1]=r[i+1][j-1][k];
						}
						r[i][j][k+1]=']';
					}

				}
			}
			if((or[i]=='(')||(or[i]=='['))
			{
				
				if(dp[i+1][j]<dp[i][j])
				{
					dp[i][j]=min(dp[i+1][j],dp[i][j])+1;
					if(or[i]=='(')
					{
						r[i][j][0]='(';
						for (k=0;;k++)
						{
							if(r[i+1][j][k]=='\0')break;
								r[i][j][k+1]=r[i+1][j][k];
						}
						r[i][j][k+1]=')';

					}
					else
					{
						r[i][j][0]='[';
						for (k=0;;k++)
						{
							if(r[i+1][j][k]=='\0')break;
								r[i][j][k+1]=r[i+1][j][k];
						}
						r[i][j][k+1]=']';
					}
				}
			}
		if((or[j]==')')||(or[j]==']'))
			{
				
				if(dp[i][j-1]<dp[i][j])
				{
					dp[i][j]=min(dp[i][j-1],dp[i][j])+1;
					if(or[j]==')')
					{
						r[i][j][0]='(';
						for (k=0;;k++)
						{
							if(r[i][j-1][k]=='\0')break;
								r[i][j][k+1]=r[i][j-1][k];
						}
						r[i][j][k+1]=')';

					}
					else
					{
						r[i][j][0]='[';
						for (k=0;;k++)
						{
							if(r[i+1][j][k]=='\0')break;
								r[i][j][k+1]=r[i][j-1][k];
						}
						r[i][j][k+1]=']';
					}
				}
				
			}
			q=j;
			for (k=i;k<j;k++)
			{					    	
				if(dp[i][k]+dp[k+1][j]<dp[i][j])
				{
					dp[i][j]=dp[i][k]+dp[k+1][j];
					q=k;
				}
			}

			if(q!=j)
			{
				for (m=0;;m++)
				{
					if(r[i][q][m]=='\0')break;
						r[i][j][m]=r[i][q][m];
				}
				for (n=0;;n++)
				{
					if(r[q+1][j][n]=='\0')break;
						r[i][j][m]=r[q+1][j][n];
					m++;
				}
			}
			

		}
	cout<<r[0][len-1]<<endl;
	return 0;
}

int min(int x,int y)
{
	if(x>y)
		return y;
	else
		return x;
}

• char or[105];就是错的 (3217) frkstyc 2008-03-25 19:34:51
  • Re:char or[105];就是错的 (27) 200694068 2008-03-25 19:37:00
    • 你不用or就好了 (31) frkstyc 2008-03-25 19:37:45
      • Re:你不用or就好了 (4) 200694068 2008-03-25 19:40:28