括号匹配

括号匹配

时间限制: 1 Sec   内存限制: 128 MB

题目描述

现在，有一行括号序列，请你检查这行括号是否配对。

输入

多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），数据保证S中只含有"[","]","(",")"四种字符。

输出

每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No。

样例输入

[(])（ (]) ([[]()])

样例输出

No No Yes

栈的实际应用，也可以用数组模拟来做（当然用的也是栈原理）#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<stack> using namespace std; char a[10005]; int main() { while(cin>>a) { stack<char>q;//定义一个字符型的栈 char t; int len,i,j,flag=0; len=strlen(a); for(i=0;i<len;i++) { if(a[i]=='('||a[i]=='[') q.push(a[i]); else if(a[i]==')'||a[i]==']') { t=q.top(); if(a[i]==')'&&t=='('||a[i]==']'&&t=='[') q.pop(); else { flag=1; break; } } } if(!q.empty()) flag=1; if(flag==1) cout<<"No"<<endl; else cout<<"Yes"<<endl; } return 0; }上面的代码在我们学校的oj可以过，南阳理工有一道一样的题，在上面提交是RuntimeError,于是又换了种写法，才在南阳oj上提交正确，与之前相比判断条件是简单了一些。

#include<stdio.h> #include<iostream> #include<string.h> #include<queue> #include<stack> #include<set> using namespace std; int main() { int n; cin>>n; char a[10005]; int len,i; while(n--) { stack<char>q; cin>>a; len=strlen(a); for(i=0;i<len;i++) { if(q.empty()) q.push(a[i]); else { if(q.top()=='('&&a[i]==')'||q.top()=='['&&a[i]==']') q.pop(); else q.push(a[i]); } } if(!q.empty()) cout<<"No"<<endl; else cout<<"Yes"<<endl; } return 0; } 再加一个扩展题，判断括号是否匹配，如果匹配的话输出括号的最大深度。 #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<stack> using namespace std; int main() { char a[105]; int b[105];//b数组就是用来保存当前括号外又包含几层括号 while(gets(a)) { stack<char>s; int i,len,temp,maxn=-1; char c; len=strlen(a); for(i=0;i<=100;i++) b[i]=0; if(a[0]==')'||len%2!=0) printf("NO\n"); else { for(i=0; i<len; i++) { if(a[i]=='(') s.push(a[i]); if(a[i]==')') { if(!s.empty()) s.pop(); else { printf("NO\n"); break; } } } if(!s.empty()) printf("NO\n"); else { printf("YES "); b[0]=1; for(i=1;i<len;i++) { if(a[i]=='(') b[i]=b[i-1]+1;// else b[i]=b[i-1]-1;//这个地方比较巧的 } sort(b,b+len); printf("%d\n",b[len-1]); } } } return 0; }