括号匹配(栈)
Time Limit: 2000/1000ms (Java/Others)
Problem Description:
给一组包含[]()两种括号的序列,检查是否是合法的。
如:()[],([]),[()]是合法的;()),[(),]()[,([)]是非法的。
输入包含多组测试数据,对于每组数据,输入一个只包含'[',']','(',')',四种字符的括号序列S(1<=length(S)<=100000);
Output:
对于每组数据,如果括号序列合法输出Yes,否则输出no。
())
[(])
([[]()])
Sample Output:
No
No
Yes解题思路:栈的运用。注意使用t.top()函数前要用t.empty()先判断是否栈空,不然会出错!AC代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 char s[100005];
4 int main(){
5 while(cin>>s){
6 stack<char> t;
7 bool flag=false;
8 for(int i=0;i<(int)strlen(s);++i){
9 if(s[i]=='[' || s[i]=='(')t.push(s[i]);
10 else if(s[i]==')'){
11 if(!t.empty() && t.top()=='(')t.pop();
12 else{flag=true;break;}
13 }
14 else{
15 if(!t.empty() && t.top()=='[')t.pop();
16 else{flag=true;break;}
17 }
18 }
19 if(flag)cout<<"No"<<endl;
20 else cout<<"Yes"<<endl;
21 }
22 return 0;
23 }