1     /**************************************************************************************    
  2     * Function     : 括号匹配 
  3     * Create Date  : 2014/05/16  
  4     * Author       : NTSK13    
  5     * Email        : beijiwei@qq.com    
  6     * Copyright    : 欢迎大家和我一起交流学习，转载请保持源文件的完整性。    
  7     *                任何单位和个人不经本人允许不得用于商业用途    
  8     * Version      : V0.1                       
  9                          
 10     题目: 经典c程序(0027)一括号匹配 
 11         现在，有一行括号序列，请你检查这行括号是否配对。  
 12         输入 : 
 13             第一行输入一个数N（0<N<=100）,表示有N组测试数据。 
 14             后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串）， 
 15             测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符  
 16      
 17         输出 : 
 18             每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No  
 19          
 20         样例输入 : 
 21                     3 
 22                     [(]) 
 23                     (]) 
 24                     ([[]()]) 
 25         样例输出 : 
 26                     No 
 27                     No 
 28                     Yes 
 29     **************************************************************************************/        
 30     #include<stdio.h>        
 31       
 32     // 测试数据可自由修改  
 33     #define COUNT   5  
 34     #define LENGTH  50  
 35       
 36     static char brackets_array[COUNT][LENGTH] =   
 37     {  
 38         "[(])",  
 39         "(])",  
 40         "([[]()])",  
 41         "([[](((()[])))[[()]]](([[()]])))",  
 42         "([[](((()[[])))[[()]]]](([[()]])))",  
 43     };  
 44       
 45     int run_test(char* pBracketString);  
 46       
 47     int main(void)  
 48     {  
 49         int i = 0;  
 50         for ( i = 0; i < COUNT; i++)  
 51         {  
 52             if (run_test(brackets_array[i]))  
 53             {  
 54                 printf("Yes");  
 55             }else  
 56             {  
 57                 printf("No");  
 58             }  
 59             printf("\n");  
 60         }  
 61     }  
 62       
 63       
 64     int run_test(char* pBracketString)  
 65     {  
 66         char *ptmp=pBracketString;  
 67         int  k=0,len=0;  
 68         char stack[LENGTH/2]={‘\0‘};  
 69         while(*ptmp !=‘\0‘)  
 70         {  
 71             ptmp++;  
 72             len++;  
 73         }  
 74         //printf("len=%d  len%2=%d\n",len,len%2);  
 75         if( len%2 )//长度为奇数  
 76             return 0;  
 77         else  
 78         {  
 79             ptmp=pBracketString;  
 80             while(*ptmp !=‘\0‘)  
 81             {  
 82     #if 1  
 83                 switch(*ptmp)  
 84                 {  
 85                     case ‘(‘:  
 86                     case ‘[‘:  
 87                         stack[k++]=*ptmp;  
 88                         break;  
 89                     case ‘)‘:  
 90                         if( stack[k-1] ==‘(‘ )  
 91                             stack[--k]=‘\0‘;  
 92                         else  
 93                             return 0;  
 94                         break;  
 95                     case ‘]‘:  
 96                         if( stack[k-1] ==‘[‘ )  
 97                             stack[--k]=‘\0‘;  
 98                         else  
 99                             return 0;  
100                         break;  
101                     default:  
102                         break;  
103                 }  
104                 ptmp++;  
105             }  
106             if(stack[0]==‘\0‘)  
107                 return 1;  
108             else  
109                 return 0;  
110     #else     
111                 if( *ptmp==‘(‘ || *ptmp==‘[‘  )  
112                 {  
113                     stack[k++]=*ptmp;  
114                     ptmp++;  
115                     continue;  
116                 }  
117               
118                 if( *ptmp==‘)‘ && stack[k-1] ==‘(‘  )  
119                 {  
120                     stack[--k]=‘\0‘;  
121                     ptmp++;  
122                     continue;  
123                 }  
124       
125                 if( *ptmp==‘)‘ && stack[k-1] !=‘(‘  )  
126                     return 0;  
127       
128                 if( *ptmp==‘]‘ && stack[k-1] ==‘[‘   )  
129                 {     
130                     stack[--k]=‘\0‘;  
131                     ptmp++;  
132                     continue;  
133                 }  
134                 if( *ptmp==‘]‘ && stack[k-1] !=‘[‘   )  
135                     return 0;  
136                   
137                 ptmp++;  
138             }  
139             if(stack[0]==‘\0‘)  
140                 return 1;  
141             else  
142                 return 0;  
143     #endif  
144           
145         }  
146     }  
147 
148