题目描述

假设表达式中允许四种括号：<>、()、[]、{}，它们的优先次序是由小到大的。其嵌套必须满足优先次序由大到小，例如：[()]或者{}或(())等都为正确的匹配。形如：([])或([)]均为错误的匹配。

编写程序判断所给的括号串是否匹配。若匹配，则输出“YES”，否则输出“NO”。

输入输出格式

输入格式：

第一行有一个数值N，它的范围是 [1...100]。

接下来有N行字符串，它是由小写字母，运算符和左右小圆括号构成，字符串长度小于255。

输出格式：

N行，输出对应行的应表达式括号是否匹配。

输入输出样例

输入样例：

5{}{}<><>()()[][]{
    {}}{
    {}}<<>><<>>(())(())[[]][[]]{
    {}}{
    {}}<<>><<>>(())(())[[]][[]]{<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]><}{
    {[]}<<<>><<>>>((<>))(())[[(<>)]][[]]

输出样例：

YESYESYESYESNO 这道题可以用栈来做，先把每个括号的优先级用数字放入栈中，一边放一边判断是否匹配，如果进入的括号的优先级大于原来栈中括号的优先级，就说明不匹配，如果括号匹配，就清除原来栈的顶部 具体程序如下：

#include
       
        #include
        
         #include
         
          #include
          
           using namespace std;string str;int n,v,now;stack
           
            s;int main(){    scanf("%d",&n);    char ch=cin.get();    for(register int i=1;i<=n;++i)    {        v=0;        getline(cin,str);        for(register int j=0;j
            
             ') now=11; if(str[j]=='(') now=2; if(str[j]==')') now=12; if(str[j]=='[') now=3; if(str[j]==']') now=13; if(str[j]=='{ ') now=4; if(str[j]=='}') now=14; if(s.empty()&&now<10) { s.push(now); continue; } else if(now>10&&s.empty()) { printf("NO\n"); v=1; break; } else if(now-10==s.top()) { s.pop(); } else if(now>s.top()) { printf("NO\n"); v=1; break; } else s.push(now); } if(v==1) { while(!s.empty()) s.pop(); continue; } if(s.empty()) printf("YES\n"); else { printf("NO\n"); } while(!s.empty()) s.pop(); } }