题目描述

输入

输出

样例输入

3
[(])
(])
([[]()])

样例输出

No
No
Yes

（本人此题用数据结构中的栈来实现，这里有一点需要注意就是第一次出现的右括号必定与其相邻的左边的括号是一定要匹配的，所以抓住这一点就有了思路，首先如果是左括号就进栈，当遇到右括号的时候就把此时的栈顶的元素与之判断，如果不相匹配就输出结果，如果相匹配就去掉此时的栈顶即出栈，然后继续上面的判断即可，最后结束的条件是如果栈空了还没有输出NO就是匹配，这里有许多的情况需要注意一下，就是有可能左括号多余或者右括号多余，在其他方面就是结构体和结构指针方面需要注意下就可以了）（本人在编写的过程中遇到的问题还是比较低级的错误的，比如判断两个括号是否匹配的时候我开始没有注意用的是ASCII码相等的时候，最后一直wronganswer，所以注意下括号匹配的条件是右括号的ASCII码比左括号的ASCII码大一或者大二）

#include<stdio.h>
#include<stdlib.h>
#define Stack_size 10000
typedef struct{char elem[Stack_size];int top;
} SeqStack; 
void InitStack (SeqStack *S) {S->top = -1;
}
int IsEmpty (SeqStack *S) {if (S->top == -1)  return 1;elsereturn 0;
}
int Push (SeqStack *S,char x) {if(S->top == Stack_size-1)  return 0;S->top++;S->elem[S->top] = x;return 0;
}
int GetTop (SeqStack *S,char *x) {if (S->top == -1)  return 0;else {*x=S->elem[S->top];return 1;}
}
int Pop (SeqStack *S,char *x) {if (S->top == -1)  return 0;else {*x=S->elem[S->top];S->top--;return 0;}
}
int Match (char a,char b){if (a+1==b||a+2==b)  return 1;else return 0;
}
int BracketMatch (char *str){SeqStack S;int i;char ch;InitStack (&S);for (i=0; str[i]!='\0'; i++){switch (str[i]) {case '(':case '[':case '{':Push (&S,str[i]);break;case ')':case ']':case '}':if (IsEmpty (&S) ){printf("No\n");return 0;}else {GetTop (&S,&ch);if (Match(ch,str[i]))Pop (&S,&ch);else{printf("No\n");return 0;}}}}if (IsEmpty (&S) )printf("Yes\n");elseprintf("No\n");return 0;
}
int main(){int n;char a[10000];scanf("%d",&n);while (n--){scanf("%s",a);BracketMatch (a);}return 0;
}