OI题库

TYVJ八月月赛提高组第1题

测试点数目：5
测试点分值：20
--内存限制：128M
--时间限制：1s

【题目描述】

定义如下括号匹配序列：
        1．空序列是匹配序列；
        2．如果S是匹配序列，那么(S),[S],{S}和也是匹配序列；
        3．如果A和B都是匹配序列，那么AB也是匹配序列。
    例如，下面的字符串都是匹配序列：
        ()，[]，(())，([])，()[]，()[()]，{{}}<>，([]<>{{}})，<<{}>>
    而以下几个则不是：
        (，[，]，)(，())，([()，<<，{(})，<{}>)
    序列中可能包含通配符，含义如下：
        /表示任意1个左括号
        #表示任意2个左括号
        @表示任意4个左括号
        ?表示任意8个左括号
        \表示任意1个右括号
        *表示任意2个右括号
        &表示任意4个右括号
        !表示任意8个右括号
    现在，给你一些由"("、")"、"["、"]"、"{"、"}"、"<"、">"和通配符构成的序列，你要做的，是判断该序列是否为匹配序列。

【输入格式】

第一行：一个正整数N，表示测试数据组数； 
接下来N行：每行一个括号序列(长度不超过L)。

【输出格式】

共N行：对于每一个括号序列，判断其是否匹配。
对于不匹配的序列，直接输出FALSE。
对于匹配的序列，输出用单一空格隔开的3个信息：
    第一个信息为TRUE
    第二个信息为括号的最大深度(层数)
    第三个信息为达到最大深度的次数
详见样例

【样例输入】

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

【样例输出】

TRUE 5 2
FALSE
TRUE 8 1

【提示】

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

数据规模：
对于20%的数据，有N=1，0 对于60%的数据，有0 对于100%的数据，有0 对于40%的数据，序列中没有通配符

【来源】

From tbcaaa8 http://www.tyvj.cn/Problem_Show.aspx?id=1590