括号序列

时间限制: 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

{()}<<>>

{{{{{}}}}

样例输出 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<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 int l,pd[4],v[3000000],top,p,d,n;
 6 int y[5]={0,'>',')',']','}'};
 7 char ch[3000000];
 8 int main(){
 9     cin>>n;
10     while(n--){
11         memset(pd,0,sizeof(pd));
12         p=0;top=0;
13         cin>>ch;
14         l=strlen(ch);
15         for(int i=0;i<l;i++){
16             switch(ch[i]){
17                 case '<':++pd[0];d=1;break;
18                 case '(':++pd[1];d=2;break;
19                 case '[':++pd[2];d=3;break;
20                 case '{':++pd[3];d=4;break;
21                 case '>':--pd[0];d=0;break;
22                 case ')':--pd[1];d=0;break;
23                 case ']':--pd[2];d=0;break;
24                 case '}':--pd[3];d=0;break;
25             }
26             if(d){v[top]=y[d];top++;}
27             else{
28             if(v[top-1]!=ch[i]){printf("FALSE
");p=1;}
29             else top--;
30             }
31             if(p) break;
32         }
33         for(int i=0;i<4;i++) if(pd[i]!=0&&!p){printf("FALSE
");p=1;}
34         if(!p) printf("TRUE
");
35     }
36     return 0;
37 }

老師佈置的題，然而之前做過了。。。