定义如下括号匹配序列:
1.空序列是匹配序列;
2.如果S是匹配序列,那么(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
栈呗。无非就是通配符再额外处理下,增加一个最大深度记录
几个括号匹配 {} [] <> ()
来个switch
再把包含通配符的字符串按规则的翻译一下
比如 {()}@<>{})))>
可以翻译成 {()}////<>{})))>
至于最大深度,可以选择在入、出栈时记录
然后就按照正常入/出栈匹配就行