1983 - 括号匹配
现在，有一行括号序列，请你检查这行括号是否配对。
Input
第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符
Output
每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No
Examples
Input
3 [(]) (]) ([[]()])
Output
No No Yes
Solution C
#include<stdio.h> #include<malloc.h> #include<string.h> #define STACK_SIZE 10005 typedef struct { char ch[10005]; int top; }Sq; Sq *Init(){ Sq *s; if(s=(Sq*)malloc(sizeof(Sq))) { s->top=0; return s;} else return NULL; } void Clear(Sq *s){ s->top=0; } void Push(Sq *s,char e){ if(s->top==STACK_SIZE) return ; else {s->ch[s->top]=e; s->top++;} } void Pop(Sq *s) { if (s->top==0) return ; s->top--; } char c[10005],p; int main(){ Sq *sq; sq=Init(); int n,l,i; scanf("%d",&n); while(n--){ scanf("%s",c); l=strlen(c); Push(sq,c[0]); for(i=1;i<l;i++){ if((c[i]==']'&&sq->ch[sq->top-1]=='[')||(c[i]==')'&&sq->ch[sq->top-1]=='('))Pop(sq); else Push(sq,c[i]); } if(sq->top==0)printf("Yes\n"); else printf("No\n"); Clear(sq); } return 0; }
Solution C++
#include<iostream> #include<cstdio> #include<cstring> char s[10000+5],strak[10000+5]; int main(){ int n; scanf("%d",&n); while(n--){ int j=0,flag=1; scanf("%s",s); for(int i=0;i<strlen(s);i++){ if(s[i]=='['){ strak[j++]=s[i]; }else if(s[i]=='('){ strak[j++]=s[i]; }else if(s[i]==']'){ if(strak[j-1]=='[') j=j-1; else{ flag=0; } }else if(s[i]==')'){ if(strak[j-1]=='(') j=j-1; else{ flag=0; } } if(!flag) break; } if(flag&& j==0) printf("Yes\n"); else printf("No\n"); } }