问题:
给你一个字符串,里面只包含"(",")","[","]"四种符号,请问你需要至少添加多少个括号才能使这些括号匹配起来。
如:
[]是匹配的,所需括号个数为 0.
([])[]是匹配的,所需括号个数为 0.
((]是不匹配的,所需最少括号个数为 3.
([)]是不匹配的,所需最少括号个数为 2.
分析:
此题来自:http://blog.csdn.net/coolanfei/article/details/7475542, 作者同时给出了正确答案。但是,感觉答案还不是特别的详细,也不是特别容易懂。所以,在此写下自己的分析思路。
1. 我们用 mb[i][j] 表示从位置 i 到字符位置 j 所需的最少括号数。假定字符串是 “[ ( )”, 那么 mb[0][0] = mb[1][1] = mb[2][2] = 1。
2. 如果我们要算mb[i][j+1], 那么,最坏的情况是使得没有被匹配的括号数增加了,即mb[i][j+1] 最多为 min(mb[i][j]
+ 1, mb[i+1][j+1] + 1). 但是,这可能不是我们想要的答案,因为在刚才的例子里,即:假定字符串是 “[ ( )”, 那么 mb[0][1] =mb[0][0]
+ 1= 2, 但是mb[1][2] 却不等于mb[1][1]
+ 1.
3.
那么,什么情况下mb[i][j+1] =mb[i][j]
+ 1?只有当 字符串里从i 到 j 没有任何字符与第 j + 1 个字符匹配的时候。但是,如果存在和第 j + 1 个字符匹配的情况,问题就不一样了。
4.
假设在i 到 j 之间存在一个字符(比如在位置 k)与第 j + 1 个字符匹配,那么我们相当于把原来的字符串分成了两个部分mb[i][k-1] 和 mb[k+1][j], 因为第k 个 和 j + 1 个字符已经匹配掉了。而且,我们不会再考虑 i 到 k - 1 的字符会和 k + 1 到 j 之间的字符匹配的情况,因为我们已经把这两个部分完全分开了(很重要的一点,这也是我当时思考很久的地方)。话句话说 mb[i][j+1] = min(
min(mb[i][j] + 1, mb[i+1][j+1] + 1), mb[i][k-1] + mb[k+1][j]).
有了这样的分析,我们可以利用动态规划的思路来解决这样的问题。代码如下:
static boolean match(char a, char b){
if(a == '(' && b == ')')
return true;
if(a == '[' && b == ']')
return true;
return false;
}
public static void minBrace(String s) {
int size = s.length();
// we begin with mb[1][1]
int[][] mb = new int[size + 1][size + 1];
for(int i = 1; i <= size; ++i){
mb[i][i] = 1;
}
// d refers to the distance between i and j, that is d = j - i
for(int d = 1; d < size; d++){
for (int i = 1; i + d <= size; i++) {
int j = i + d;
// the worst case
mb[i][j] = Math.min(mb[i][j - 1], mb[i + 1][j]) + 1;
// the case in which a char between i and j (= i + d) matches
// the character at position j + 1
for (int k = i ; k <= j - 1; k++ ) {
if (match(s.charAt(k - 1), s.charAt(j - 1)) == true) {
mb[i][j] = Math.min(mb[i][j], mb[i][k - 1] + mb[k + 1] [j - 1]);
}
}
}
}
System.out.println(mb[1][size]);
}
转载请注明出处:http://blog.csdn.net/beiyeqingteng
分享到:
相关推荐
给定一个字符串,其中的字符只包含三种括号:花括号{ }、中括号[ ]、圆括号( ),即它仅由 “( ) [ ] { }” 这六个字符组成。设计算法,判断该字符串是否有效,即字符串中括号是否匹配。括号匹配要求括号必须以正确的...
请写一个程序,判断给定表达式中的括号是否匹配,既左右括号顺序和数量都匹配。 输入说明 输入为一个表达式字符串,长度不超过50。 输出说明 对输入的表达式,若其中的括号是匹配的,则输出“yes”,否则...
本程序时对一个字符串,判断其中括号(小,中,大括号)是否匹配
java字符串处理取出括号内的字符串 都是我自己试过可以用的j
ACM 在线测评第二题,括号配对!表示完全是自己写的,没有参考他人思想!有不足之处请指正!
判断给定表达式中的括号是否匹配,表达式中的合法括号为”(“, “)”, “[", "]“, “{“, ”}”,这三个括号可以按照任意的次序嵌套使用。
给定一个由 '(' 和 ')' 括号组成的字符串 S,我们需要添加最少的括号( '(' 或是 ')',可以在任何位置),以使得到的括号字符串有效。 从形式上讲,只有满足下面几点之一,括号字符串才是有效的: 它是一个空字符串...
c++代码,算法写的非常详细,需要的同学拿去,海师的别下,免得雷同。
利用栈编写满足下列要求的括号匹配检验程序:假设表达式中允许包含两种括号:圆括号和方括号,其嵌套的顺序随意,即([]())或[([][])]等为正确的格式,[(]或([())或(()])均为不正确的格式。输入一个包含上述括号的...
对于给定的表达式通过+和*来运算,求出最小值并添加括号
数据结构括号匹配程序c语言试验程序,实现括号自动匹配,支持文件操作20字符以内文件名。
自己做的,能用栈实现括号匹配,程序很简单实用
代码均为自己设计所写,分享一下。 字符串数学表达式(含括号)计算值 如: "31+3*3-20/2*5+40/8+4*5" ((2*(19-13*(1+2)/39)/6+4)-5)/5+((2+3)*2-5)
C#版的检测括号是否匹配的问题,可以检测出从键盘输入的一串字符,其中有字母、数字和其它一些特殊符号,这一串字符中有小括号,中括号,通过本程序,可以判断出输入入的字符串中的小、中括号是否匹配,是缺少左小、...
上机作业,自己做的 不是很好!实现的就是{【(之间匹配的问题~~ 也希望大家可以帮忙修改。
1.(),[]是括号匹配的字符串 2.若A是括号匹配的串,则(A),[A]是括号匹配的字符串 3.若A,B是括号匹配的字符串,则AB也是括号匹配的字符串
任意输入一个由若干个圆括号、方括号和花括号组成字符串,设计一个算法判断该串中的括号是否配对。
括号匹配问题
regex:(way|zgw) result:结果是可以匹配出way的,因为是多选结构,小括号是匹配字符串的 示例2:string text = “123456789”; regex:(0-9) result:结果是什么都匹配不到的,它只匹配字符串”0-9″而不是...
利用栈实现括号匹配的检验,存储括号字符的数组通过malloc实现动态分配长度,匹配函数的第一个参数为指向字符的指针(即为存储括号字符的数组的首地址)和一个整数(即为括号字符的总数,为括号个数的2倍),将左...