题目名称 1214. [Tyvj Aug11] 括号匹配
输入输出 kakko.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 5 简单对比
题目来源 2012-10-24
开放分组 全部用户
提交状态
分类标签
栈和队列
通过:18, 提交:129, 通过率:13.95%
Gravatar再见 100 0.182 s C++
GravatarMakazeu 100 0.255 s C++
Gravatarrvalue 100 0.269 s C++
Gravatar邵平 :your DAD☭ 100 0.318 s C++
Gravatar邵平 :your DAD☭ 100 0.329 s C++
GravatarPaulinsider 100 0.348 s C++
Gravatarwolf 100 0.349 s C++
GravatarPaulinsider 100 0.356 s C++
Gravatar邵平 :your DAD☭ 100 0.368 s C++
Gravatar邵平 :your DAD☭ 100 0.428 s C++
关于 括号匹配 的讨论
在tyvj上超時了。。。在COGS上AC了。。。無語。。
GravatarMakazeu
2012-10-26 09:38 1楼
1000 0000的数据吃了不少内存,题目上竟然没说!!
Gravatarwolf
2014-04-19 22:08 2楼
写代码要循序渐进,就这样。ps(我的代码好慢QAQ...)
Gravatarraywzy
2014-06-29 20:33 3楼
改用fin和fout
Gravatar邵平 :your DAD☭
2018-08-07 20:22 4楼

1214. [Tyvj Aug11] 括号匹配

★☆   输入文件:kakko.in   输出文件:kakko.out   简单对比
时间限制:1 s   内存限制:128 MB
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