、字符串匹配问题
【问题描述】
字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式,从内到外必须是<>,(),[],{},例如。输入: [()] 输出:YES,而输入([]), ([])都应该输出NO。
【输入格式】strs.in
文件的第一行为一个整数n,表示以下有多少个由括好组成的字符串。接下来的n行,每行都是一个由括号组成的长度不超过255的字符串。
【输出格式】strs.out
在输出文件中有N行,每行都是YES或NO。
【输入样例】
5
{}{}<><>()()[][]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
【输出标例】
YES
YES
YES
YES
NO
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 char c[10000001];
6 int topa=0;
7 int topb=0;
8 int topc=0;
9 int topd=0;
10 int main()
11 {
12 int n;
13 cin>>n;
14 for(int i=1;i<=n;i++)
15 {
16 int flag=1;
17 scanf("%s",&c);
18 for(int i=0;i<=strlen(c)-1;i++)
19 {
20 if(c[i]=='(')
21 topa++;
22 else if(c[i]=='[')
23 topb++;
24 else if(c[i]=='{')
25 topc++;
26 else if(c[i]=='<')
27 topd++;
28 else if(c[i]==')')
29 {
30 if(topa>0)
31 topa--;
32 else
33 {
34 cout<<"NO"<<endl;
35 flag=0;
36 break;
37 }
38 }
39 else if(c[i]==']')
40 {
41 if(topb>0)
42 topb--;
43 else
44 {
45 cout<<"NO"<<endl;
46 flag=0;
47 break;
48 }
49 }
50 else if(c[i]=='}')
51 {
52 if(topc>0)
53 topc--;
54 else
55 {
56 cout<<"NO"<<endl;
57 flag=0;
58 break;
59 }
60 }
61 else if(c[i]=='>')
62 {
63 if(topd>0)
64 topd--;
65 else
66 {
67 cout<<"NO"<<endl;
68 flag=0;
69 break;
70 }
71 }
72 }
73 if(flag==1)
74 {
75 if(topa==0&&topb==0&&topc==0&&topd==0)
76 cout<<"YES"<<endl;
77 else
78 cout<<"NO"<<endl;
79 }
80
81 }
82
83 return 0;
84 }
85