1214. [Tyvj Aug11] 括号匹配

【题目描述】

定义如下括号匹配序列：
   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<L≤20。

对于60%的数据，有0<N≤5，0<L≤2e3。

对于100%的数据，有0<N≤10，0<L≤2e6.

对于40%的数据，序列中没有通配符。

【来源】

From TYVJ八月月赛提高组第1题 http://www.tyvj.cn/Problem_Show.aspx?id=1590