RYIP在线题库
首 页   >   习题练习   >   提交
Problem1708--2021第四届RYIP活动X组(小学组)试题二

1708: 2021第四届RYIP活动X组(小学组)试题二

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

括号匹配 

定义如下括号匹配序列:
1.空序列是匹配序列;
2.如果S是匹配序列,那么(S),[S],{S}和<S>也是匹配序列;
3.如果A和B都是匹配序列,那么AB也是匹配序列。
例如,下面的字符串都是匹配序列:
(),[],(()),([]),()[],()[()],{{}}<>,([]<>{{}}),<<{}>>

而以下几个则不是:
(,[,],)(,()),([(),<<,{(}),<{}>)
序列中可能包含通配符,含义如下:
    /表示任意1个左括号
    #表示任意2个左括号
    @表示任意4个左括号
    ?表示任意8个左括号
    \表示任意1个右括号
    *表示任意2个右括号
    &表示任意4个右括号
    !表示任意8个右括号
现在,给你一些由"("、")"、"["、"]"、"{"、"}"、"<"、">"和通配符构成的序列,你要做的,是判断该序列是否为匹配序列。


【 Input 】

第一行:一个正整数N,表示测试数据组数; 

接下来N行:每行一个括号序列(长度不超过L)

【 Output 】

共N行:对于每一个括号序列,判断其是否匹配。

对于不匹配的序列,直接输出FALSE
对于匹配的序列,输出用单一空格隔开的3个信息:
第一个信息为TRUE
第二个信息为括号的最大深度(层数)
第三个信息为达到最大深度的次数
详见样例


【 Sample Input 】

3
{()}@<>{})))>
([})
?\\\\\\\]	

【 Sample Output 】

TRUE 5 2
FALSE
TRUE 8 1

【HINT】

【样例说明】

对于第一组数据,@相当于<(((,是匹配的,括号的最大深度为5,该深度出现了2次。
对于第二组数据,[}不匹配。
第三组数据想要说明的是,通配符间可以匹配。

【数据范围】

对于20%的数据,有N=10<L<=20
对于60%的数据,有0<N<=50<L<=2E+3
对于100%的数据,有0<N<=100<L<=2E+6
对于40%的数据,序列中没有通配符


【 Source/Category 】