南阳理工ACM 括号匹配问题,并求出使得括号能够匹配需要新增的最小括号数(括号匹配(二))

描述

给你一个字符串,里面只包含"(",")","[","]"四种符号,请问你需要至少添加多少个括号才能使这些括号匹配起来。
如:
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的

输入
第一行输入一个正整数N,表示测试数据组数(N<=10)
每组测试数据都只有一行,是一个字符串S,S中只包含以上所说的四种字符,S的长度不超过100
输出
对于每组测试数据都输出一个正整数,表示最少需要添加的括号的数量。每组测试输出占一行
样例输入
4
[]
([])[]
((]
([)]
样例输出
0
0
3
2

解题思路

        如果仅仅是一般的判断括号是否匹配,直接扫描一遍数组,利用一个栈就可以判定YES还是OR。现在需要求解其输出的个数。可以联想到我们求解矩阵连乘问题,求解何种组合使得计算量最小。利用动态规划的方式求解。

        利用公式:M[i,j]=M[i,k]+M[k+1,j](k={i,i+1,...j-1})

         

 //括号匹配问题 求最大子长 M[i,j]=min(M[i,j],M[i,k]+M[k+1,j]
class Program
{
static void Main(string[] args)
{
string S = "((]";
int[,] M = new int[S.Length, S.Length];
for (int i = ; i < S.Length; i++)
for (int j = ; j < S.Length; j++)
M[i, j] = -;
Console.WriteLine(NeedLength(, S.Length - , S, M));
for (int i = ; i < S.Length; i++)
{
Console.WriteLine();
for (int j = ; j < S.Length; j++)
Console.Write(M[i, j] + " ");
}
Console.Read();
}
//判定是否匹配
public static bool isMatch(char x, char y)
{
bool flag = false;
if ((x == '(' && y == ')') || (x == '[' && y == ']'))
flag = true;
return flag;
}
/// <summary>
/// 求解需要的最少括号数
/// </summary>
/// <param name="i">从I开始</param>
/// <param name="j">到j结束</param>
/// <param name="S">匹配数组</param>
/// <param name="M">保存i---j需要次数的数组</param>
/// <returns></returns>
public static int NeedLength(int i, int j, string S, int[,] M)
{
int ans = ;
if (M[i, j] != -)
return M[i, j];
if (i == j)
{
return ;
}
if (i > j)
return ;
if (isMatch(S[i], S[j]))//如果匹配,则直接i往后移,j往前移
{
ans = Math.Min(ans, NeedLength(i + , j - , S, M));
}
for (int k = i ; k < j; k++)//求解哪个分解之后,使得结果最小化
{
ans = Math.Min(ans, NeedLength(i, k, S, M) + NeedLength(k + , j, S, M));
}
M[i, j] = ans;
return M[i, j];
}
}
上一篇:矩形嵌套 南阳理工ACM


下一篇:(中等) HDU 4725 The Shortest Path in Nya Graph,Dijkstra+加点。