#B4417. 括号匹配

括号匹配

题目描述

给定只由 6 种括号字符组成的字符串:(, ), [, ], {, }。判断每个字符串是否为“合法括号序列”,合法则输出 YES,否则输出 NO。合法括号序列的定义:

  • 空串合法;
  • 若 A 合法,则 (A), [A], {A} 均合法;
  • 若 A 与 B 均合法,则 AB 合法。

输入格式

第一行一个整数 TT,表示数据组数。接下来 TT 行,每行一个只包含上述 66 种字符的字符串。

输出格式

对于每个字符串,输出一行:

  • 若其为合法括号序列,输出 YES;
  • 否则输出 NO。
1
()[]{}
YES
6
()
([)]
([]){}
((((
{[()()]}
}{
YES
NO
YES
NO
YES
NO

提示

记单串长度记为 S|S|。测试数据满足 1S1061 \leq |S| \leq 10^61T2×1051 \leq T \leq 2\times 10^5,同一输入文件内总长度 S2×106\sum |S| \leq 2\times 10^6,字符串只包含字符 ()[]{}