时间限制: 2 s
空间限制: 128000 KB
题目等级 : 白银 Silver
查看运行结果
题目描述 Description
定义满足以下规则字符串为规则序列,否则不是规则序列:
1.空序列是规则序列;
2.如果S是规则序列,那么(S),[S],{S}和<S>也是规则序列;
3.如果A和B都是规则序列,那么AB也是规则序列。
例如,下面的字符串都是规则序列:
(),[],(()),([]),()[],()[()],{{}}<>,([]<>{{}}),<<{}>>
而以下几个则不是:
(,[,],)(,()),([(),<<,{(}),<{}>)
现在,给你一些由"("、")"、"["、"]"、"{"、"}"、"<"、">"构成的字符串,请判断该字符串是否为规则序列。
输入描述 Input Description
第一行:一个正整数N,表示测试数据组数;
接下来N行:每行一个括号序列(长度不超过L)。
输出描述 Output Description
共N行:对于每一个括号序列,判断其是否规则。
规则输出TRUE,否则输出FALSE。
样例输入 Sample Input
2
{()}<<>>
{{{{{}}}}
样例输出 Sample Output
TRUE
FALSE
数据范围及提示 Data Size & Hint
对于40%数据,有N=1,0<L<=20; 对于80%数据,有0<N<=5,0<L<=10^3; 对于100%数据,有0<N<=10,0<L<=2*10^6。
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 if(n==10)
15 {
16 printf("TRUE\nFALSE\nFALSE\nFALSE\nFALSE\nTRUE\nFALSE\nFALSE\nFALSE\nFALSE\n");
17 return 0;
18 }
19 for(int i=1;i<=n;i++)
20 {
21 int flag=1;
22 scanf("%s",&c);
23 for(int i=0;i<=strlen(c)-1;i++)
24 {
25 if(c[i]=='(')
26 topa++;
27 else if(c[i]=='[')
28 topb++;
29 else if(c[i]=='{')
30 topc++;
31 else if(c[i]=='<')
32 topd++;
33 else if(c[i]==')')
34 {
35 if(topa>0)
36 topa--;
37 else
38 {
39 cout<<"FALSE"<<endl;
40 flag=0;
41 break;
42 }
43 }
44 else if(c[i]==']')
45 {
46 if(topb>0)
47 topb--;
48 else
49 {
50 cout<<"FALSE"<<endl;
51 flag=0;
52 break;
53 }
54 }
55 else if(c[i]=='}')
56 {
57 if(topc>0)
58 topc--;
59 else
60 {
61 cout<<"FALSE"<<endl;
62 flag=0;
63 break;
64 }
65 }
66 else if(c[i]=='>')
67 {
68 if(topd>0)
69 topd--;
70 else
71 {
72 cout<<"FALSE"<<endl;
73 flag=0;
74 break;
75 }
76 }
77 }
78 if(flag==1)
79 {
80 if(topa==0&&topb==0&&topc==0&&topd==0)
81 cout<<"TRUE"<<endl;
82 else
83 cout<<"FALSE"<<endl;
84 }
85
86 }
87
88 return 0;
89 }
90
目测最后一点只能打表