括号配对-栈的运用

题目:
第一行输入一个数N(0<N<=100),表示有N组测试数据。后面的N行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),
测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符

 
解决这道题,首先要知道括号配对满足的条件是什么。  
1.左括号与右括号个数相等  
2.左右括号配对次序正确  
解决这道题要用到“栈”  

输入字符串   从开始往后查 当遇到左括号时将之进入栈,继续往后查 当遇到右括号时就要与“栈”的首个比较看是否配对  
当配对时 将配对的符号从栈中取出,不配对时即break;  
以下两种情况还需特判一下   
1.字符最后一个判断完了  但最后栈里是否还有。  
2.栈里没有了 但查到了右括号即无法找到栈中左括号  
上代码
#include<stdio.h>  
#include<string.h>  
char zhan[10010];////进栈  
char s[10010];  
int main()  
{  
    int t,k,len,sign;//len用于判断是否停止  
    scanf("%d",&t);  
    while(t--)  
    {  
       scanf("%s",s);  
       len=strlen(s);  
       k=-1;sign=1;  
       for(int i=0;i<len;i++)  
       {  
           if(s[i]=='['||s[i]=='(')//入栈  
                zhan[++k]=s[i];  
           else  if((s[i]==']'&&k!=-1&&zhan[k]=='[')||(s[i]==')'&&k!=-1&&zhan[k]=='('))////进栈查找  
                   zhan[k--]='';  
           else//查找不符合  
                 {  
                     sign=0;  
                      break;  
                 }  
             if(i==len-1&&k!=-1)//最后一个查完 了但栈里还有的情况  
             {  
                 sign=0;  
                 break;  
             }  
       }  
       if(sign==1)  
        printf("Yes
");  
       else  
        printf("No
");  
       memset(s,0,sizeof(s));  
    }  
}  

如有细节错误请在下方评论指出,本人将不胜感激。


原文地址:https://www.cnblogs.com/dchnzlh/p/9780095.html