ACM之括号匹配（二）

/*

ACM的括号匹配（二）

*/

#include <iostream>

#include <string>

using namespace std;

//判断传入的两个字符是否匹配

bool Matched(char a, char b)

{

if((a == '(' && b == ')') || (a == '[' && b == ']'))

return true;

return false;

}

int main()

{

const int ARRCUT = 100; //二维数组的大小

//beg:表示开始的字符 end表示结束的字符 index好似一个寻找匹配符号的索引器（或游标） arr：一个二维数组

int N, i, beg, end, index, arr[ARRCUT][ARRCUT];

string S;

cin >> N;

while(N--)

{

cin >> S;

//因为不存在空串，所以如果该字符串只有1个字符，可直接输出需要匹配的括号数量为1

if(S.size() == 1)

{

cout << 1 << endl;

continue;

}

//memset方法不给用（用了会报错，郁闷,所以自己动手吧）将数组的数据全部赋为0

for(beg = 0; beg < ARRCUT; ++beg)

for(end = 0; end < ARRCUT; ++end)

arr[beg][end] = 0;

//表示自己到自己的匹配数为1

for(i = 0; i < ARRCUT; ++i)

arr[i][i] = 1;

//下面开始真正的匹配工作了，把end指到第二个字符

for(end = 1; end < S.size(); ++end)

{

//把beg指到end的前面一个字符

for(beg = end - 1; beg >= 0; --beg)

{

//先求出从beg到end之间的匹配数（简称匹配数）吧，就是在（从beg到end减一的距离）之上加1

arr[beg][end] = arr[beg][end - 1] + 1;

//把游标指向beg的位置，开始向后不断地寻找和end相匹配的符号

for(index = beg; index < end; ++index)

{

//如果找到了匹配的符号

if(Matched(S[index], S[end]))

{

//如果游标的位置等于beg的位置，说明游标还没有移动过

if(index == beg)

//就把匹配数改写成从游标的下一位置开始到end前面一个字符之间的数字吧

arr[beg][end] = arr[index + 1][end - 1];

else

//否则，就是游标移动了，那么匹配数就得再加上beg位置到游标之前位置的数量了

arr[beg][end] = min(arr[beg][end], arr[beg][index - 1] + arr[index + 1][end -1]);

}

}

}

}

//输出也写一下吧，输出从第一个字符开始直到最后一个字符之间需要匹配的符号数：）

cout << arr[0][S.size() - 1] << endl;

}

return 0;

}

</string></iostream>