#include <cstdio>
#include <string>
#include <iostream>
#define INF 1e9
using namespace std;
struct node
{
    int x,y;
};
int dp[105][105];
node path[105][105];
string s;
void print(int a,int b)
{
    if (a > b)
        return;
    if (a == b)
    {
        if (s[a] == '(' || s[a] == ')')
            printf("()");
        else
            printf("[]");
        return;
    }
	if (path[a][b].x == 1 && path[a][b].y == -1)
	{
		putchar(s[a]);
        print(a + 1,b - 1);
        putchar(s[b]);
        return;
	}
    if (path[a][b].x == a + 1)
    {
		if (s[a] == '(' || s[a] == ')')
			printf("()");
		else
			printf("[]");
		print(a + 1,b);
		return;
    }
    if (path[a][b].x == b)
    {
        print(a,b - 1);
        if (s[b] == '(' || s[b] == ')')
            printf("()");
        else
            printf("[]");
        return;
    }
    if (path[a][b].x < 0)
    {
        int r = -path[a][b].x;
        print(a,r - 1);
        print(r,b);
    }
    return;
}
int main()
{
    int i,j,k,i1;
	char s1[105];
	while (gets(s1))
	{
		if (strlen(s1) == 0)
		{
			printf("\n");
			continue;
		}
		s = s1;
		memset(dp,0,sizeof(dp));
		memset(path,0,sizeof(path));
		k = s.length();
		for (j = 0;j < k;j++)
		{
			for (i = 0;i < k;i++)
			{
				if (i + j >= k)
					break;
				dp[i][i + j] = INF;
				if (j == 0)
				{
					dp[i][i] = 2;
					continue;
				}
				if (s[i] == ')' || s[i] == ']')
				{
					dp[i][i + j] = dp[i][i] + dp[i + 1][i + j];
					path[i][i + j].x = i + 1;
					continue;
				}
				if (s[i + j] == '(' || s[i + j] == '[')
				{
					dp[i][j] = dp[i][i + j - 1] + dp[i + j][i + j];
					path[i][i + j].x = i + j;
					continue;
				}
				if (s[i] == '(' && s[i + j] == ')' && dp[i + 1][i + j - 1] + 2 < dp[i][i + j])
				{
					dp[i][i + j] = dp[i + 1][i + j - 1] + 2;
					path[i][i + j].x = 1,path[i][i + j].y = -1;
				}
				else if (s[i] == '[' && s[i + j] == ']' && dp[i + 1][i + j - 1] + 2 < dp[i][i + j])
				{
					dp[i][i + j] = dp[i + 1][i + j - 1] + 2;
					path[i][i + j].x = 1,path[i][i + j].y = -1;
				}
				for (i1 = i + 1;i1 < i + j;i1++)
				{
					if (((s[i] == '(' && s[i1] == ')') || (s[i] == '[' && s[i1] == ']') )&& dp[i][i1] + dp[i1 + 1][i + j] < dp[i][i + j])
					{
						dp[i][i + j] = dp[i][i1] + dp[i1 + 1][i + j];
						path[i][i + j].x = -(i1 + 1);
					}
					if (((s[i1] == '(' && s[i + j] == ')') || (s[i1] == '[' && s[i + j] == ']') )&& dp[i][i1 - 1] + dp[i1][i + j] < dp[i][i + j])
					{
						dp[i][i + j] = dp[i][i1 - 1] + dp[i1][i + j];
						path[i][i + j].x = -i1;
					}
				}
				if (dp[i][i] + dp[i + 1][i + j] < dp[i][i + j])
				{
					dp[i][i + j] = dp[i][i] + dp[i + 1][i + j];
					path[i][i + j].x = i + 1;
				}
			}
		}
		print(0,k - 1);
		printf("\n");
	}
    return 0;
}

• Re:为什么错了，求指点。。。。附代码 (3144) mlz000 2012-02-19 21:57:01