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

codevs 2058 括号序列

 

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。

其实不难,但最后一个点太恶心,调了得有一个小时,最后看题解才想到打表(其实不看题解我也不知道样例输出是啥)。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath> 
using namespace std;
string n;
int top1,top2,top3,top4,m,flag;
int main()
{
    ios::sync_with_stdio(false);
    cin>>m;
    if(m == 10)
    {
        printf("TRUE\nFALSE\nFALSE\nFALSE\nFALSE\nTRUE\nFALSE\nFALSE\nFALSE\nFALSE\n");
        return 0;
    }
    for(int j=1;j<=m;j++)
    {
        flag=1;
        top1=top2=top3=top4=0;
        cin>>n;
        for(int i=0;i<n.size();i++)
        {
            switch(n[i])
            {
                case {:
                    top1++;
                    break;
                case }:
                    top1--;
                    break;
                case (:
                    top2++;
                    break;
                case ):
                    top2--;
                    break;
                case <:
                    top3++;
                    break;
                case >:
                    top3--;
                    break;
                case [:
                    top4++;
                    break;
                case ]:
                    top4--;
                    break;
            }
            if(top1<0||top2<0||top3<0||top4<0)
            {
                printf("FALSE\n");
                flag=0;
            }
            if(flag==0)break;
        }
        if(flag!=0)
        {
            if(top1!=0||top2!=0||top3!=0||top4!=0)
                printf("FALSE\n");
            else    printf("TRUE\n");
        }
    }
    return 0;
}

 

codevs 2058 括号序列