1355：字符串匹配问题(strs)
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是<>,(),[],{}，例如。输入: [()] 输出:YES，而输入([])，([)]都应该输出NO。
【输入】
第一行为一个整数n，表示以下有多少个由括好组成的字符串。接下来的n行，每行都是一个由括号组成的长度不超过255的字符串。
【输出】
在输出文件中有n行，每行都是YES或NO。
【输入样例】
5
{}{}<><>()()[][]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
【输出样例】
YES
YES
YES
YES
NO
1. #include <iostream> 2. #include <cstdio> 3. #include <cstring> 4. #include <stack> 5. using namespace std; 6. char ch[260]; 7. int a[260]; 8. void pri(int l){ 9. memset(a,0,sizeof(a)); 10. for(int i=0;i<l;i++){ 11. switch(ch[i]) 12. { 13. case '{':a[i]=1;break; 14. case '[':a[i]=2;break; 15. case '(':a[i]=3;break; 16. case '<':a[i]=4;break; 17. case '>':a[i]=5;break; 18. case ')':a[i]=6;break; 19. case ']':a[i]=7;break; 20. case '}':a[i]=8;break; 21. } 22. } 23. } 24. int main(int argc, char *argv[]) 25. { 26. int n,i,j; 27. cin>>n; 28. for(j=1;j<=n;j++){ 29. cin>>ch; 30. int l=strlen(ch); 31. pri(l); 32. stack<int> s; 33. s.push(0); 34. for(i=0;i<l;i++){ 35. if(a[i]<5) 36. if(a[i]>=s.top())s.push(a[i]); 37. else break; 38. else 39. if(a[i]+s.top()==9)s.pop(); 40. else break; 41. } 42. if((i==l)&&(s.size()==1))cout<<"YES"<<endl; 43. else cout<<"NO"<<endl; 44. } 45. return 0; 46. }
1. #include <iostream> 2. #include <cstdio> 3. #include <stack> 4. using namespace std; 5. string s1="{[(<"; 6. string s2="}])>"; 7. void check_sign(string &exp) 8. { 9. stack<int> stk; 10. for(int i=0;i<exp.size();i++){ 11. int pos; 12. if((pos=s1.find(exp[i]))!=string::npos){ 13. if(stk.size() && stk.top()>pos){ 14. cout<<"NO"<<endl; return; 15. } 16. else stk.push(pos); 17. } 18. else if((pos=s2.find(exp[i]))!=string::npos){ 19. if(!stk.size() || (stk.size() && stk.top()!=pos)) { 20. cout<<"NO"<<endl; return; 21. } 22. else stk.pop(); 23. } 24. } 25. if(!stk.size()) cout<<"YES"<<endl; 26. else cout<<"NO"<<endl; 27. } 28. int main(int argc, char *argv[]) 29. { 30. int n; 31. cin>>n; 32. while(n-- > 0){ 33. string exp; 34. cin>>exp; 35. check_sign(exp); 36. } 37. return 0; 38. }
