NYOJ  15 括号匹配
给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。
如：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的
输入
第一行输入一个正整数N，表示测试数据组数(N<=10)
每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100
输出
对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行
样例输入
4
[]
([])[]
((]
([)]
样例输出
0
0
3
2
去年暑假，就在思考这个问题，今天终于解决了。
[cpp] view plaincopy
1. #include <iostream> 
2. #include <cstdio> 
3. #include <cstring> 
4. using namespace std; 
5. #define N 102 
6. #define INF 1e9 
7. int result[N][N];//保存从i 到 j所需要的最少括号数 
8. char s[N]; 
9. int Min(int i,int j) 
10. { 
11.    if(result[i][j]!=INF) 
12.       return result[i][j]; 
13.    else 
14.    { 
15.       for(int t=i;t<j;t++) 
16.       { 
17.          int tempa=Min(i,t); 
18.          int tempb=Min(t+1,j); 
19.          //如果第i 和 第j 匹配的话，那么result[i][j]=result[i+1][j-1] 
20.          if(s[i-1]=='('&&s[j-1]==')'||(s[i-1]=='['&&s[j-1]==']')) 
21.            result[i][j]=min(result[i][j],result[i+1][j-1]); 
22.              
23.            result[i][j]=min(result[i][j],tempa+tempb); 
24.       } 
25.       return result[i][j]; 
26.    } 
27. } 
28. int main() 
29. { 
30.    int n,T,i,j; 
31.    cin>>T; 
32.    while(T--) 
33.    { 
34.       scanf("%s",s); 
35.       n=strlen(s); 
36.       for(i=1;i<=n;i++) 
37. 正则匹配括号里的内容         for(j=i+1;j<=n;j++) 
38.          { 
39.            result[i][j]=INF; 
40.          } 
41.       result[n][n]=1; 
42.       for(i=1;i<n;i++) 
43.       { 
44.          result[i][i]=1; 
45.          result[i+1][i]=0; 
46.       } 
47.       cout<<Min(1,n)<<endl; 
48.     /*  cout<<"************"<<endl; 
49.       for(i=1;i<=n;i++) 
50.        { 
51.  
52.           for(j=1;j<=n;j++) 
53.          { 
54.            cout<<result[i][j]<<" "; 
55.          } 
56.          cout<<endl; 
57.        }*/ 
58.    } 
59.     return 0; 
60. } 

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。