[Tyvj Aug11]括号匹配

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 kakko.in 输出文件 kakko.out
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