给定只由 6 种括号字符组成的字符串：(, ), [, ], {, }。判断每个字符串是否为“合法括号序列”，合法则输出 YES，否则输出 NO。
输入 #2
6
()
([)]
([]){}
((((
{[()()]}
}{
输出 #2
YES
NO
YES
NO
YES
NO
题解
对于一个右括号，它如果能够被匹配，那么只能与它左边最近的尚未匹配的左括号匹配。
因此我们只需要维护这些尚未匹配的左括号，并且每次只关心最后加入的一个。
我们可以用如下的方式维护：
char stk[10000];
int top = 0;
stk[top] = c; top++; // 加入一个尚未匹配的左括号
top--; // 匹配一个括号
这种结构被称为栈。stk[top-1] 所对应的字符即为最后一个未匹配的左括号。
对于当前字符：
-
如果是
(、[、{，直接压入栈中； -
如果是
)、]、}：-
如果栈为空，说明这个右括号找不到对应的左括号，序列非法；
-
否则检查栈顶：
-
)必须对应(； -
]必须对应[； -
}必须对应{。
-
-
如果类型不同，则序列非法；
-
如果类型相同，则弹出栈顶。
-
扫描结束后，还需要检查栈是否为空。
如果栈不为空，说明还有左括号没有被匹配，例如：
(([]
因此只有在扫描过程中没有发生失配，并且最终栈为空时，括号序列才合法。
参考代码如下
作者：刘向奥
#include <stdio.h>
#include <string.h>
char a[1000010];
char stk[1000010]; int top = 0;
void solve()
{
top = 0;
scanf("%s", &a);
int len = strlen(a);
for(int i = 0; i < len; i++)
{
char c = a[i];
if (c == '(' || c == '[' || c == '{')
{
stk[top] = c; top++;
}else // ) ] }
{
if(top == 0
|| (c == ')' && stk[top-1] != '(')
|| (c == ']' && stk[top-1] != '[')
|| (c == '}' && stk[top-1] != '{') )
{
printf("NO\n");
return;
}
top--;
}
}
if(top != 0) printf("NO\n");
else printf("YES\n");
}
int main()
{
int t; scanf("%d", &t);
for(int i = 0; i < t; i++)
{
solve();
}
}