首页 > 代码库 > 2058 括号序列

2058 括号序列

2024-09-10 21:30:10   221人阅读

2058 括号序列

 

 时间限制: 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                 else38                 {39                     cout<<"FALSE"<<endl;40                     flag=0;41                     break;42                 }43             }44             else if(c[i]==‘]‘)45             {46                 if(topb>0)47                 topb--;48                 else49                 {50                     cout<<"FALSE"<<endl;51                     flag=0;52                     break;53                 }54             }55             else if(c[i]==‘}‘)56             {57                 if(topc>0)58                 topc--;59                 else60                 {61                     cout<<"FALSE"<<endl;62                     flag=0;63                     break;64                 }65             }66             else if(c[i]==‘>‘)67             {68                 if(topd>0)69                 topd--;70                 else71                 {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

目测最后一点只能打表

2058 括号序列


联系
我们