对ACM仰慕已久，无奈今天才开始。好吧，遇到的第二个题目就把我难到了。（实话是第一个）
进入正题，下面Copy出题目：
- 现在，有一行括号序列，请你检查这行括号是否配对。
- 输入
- 第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符 输出
- 每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No 样例输入
-
3[(])(])([[]()])
样例输出 -
NoNoYes 拿到该题目的时候，想的最多的当然是括号匹配的问题，并没有思考其他的。以下是我思考的过程： 随便写一个很长的括号匹配的例子来找到其中的规律。如下： [([()])()] 欣喜若狂，找到了如下的规律： ====================================================================================================== 1.如果这个字符串的长度为奇数，不用看了，这个字符串已经不可能匹配了。所以会用到strlen()函数。 2.对于满足偶数条件的，那就从第一个字符开始查找。先找第一个，再找第二个： 若第一个和第二个不匹配，表明从最后一个括号肯定是匹配的，所以开始匹配判断。（以此类推）。 ====================================================================================================== 当深入分析的时候，发现，好吧，该模型太理想化了，不行。存在严重的错误，只有当该括号完全中心轴对称才会满足这种情况，PASS。 所以，我又想了一下其他的，终于，考虑到递归+消除的思想，想到了一个绝佳的点子： ======================================================================================================= 1.递归-->解析到最小解； 2.消除-->匹配以后我就不用管了。 =========================================================================== 在括号匹配中，总会有这种情况出现：()或[]。当把这一部分消除以后，剩下的部分也总是会出现()或[]。 那么，是否可以将此作为一个单位消除掉，直到最后整个序列全部消除？我想应该是可以的。 但是，如何去实现这一部分？采用什么方式去实现，又是一个头疼的问题。 这让我联想到了播放音乐时候的“节奏条”（姑且这么称呼吧），可以大，可以小，最后可以没有。 所以，我需要两个部分。 1.字符串首地址指针。 2.移动指针。 总觉得少了一点什么，怎么去表示删除的字符呢？在原字符串中可以表示吗？又是一个难题。需要去解决，于是想到了其他的解决方案： 将字符串序列中的第一位开始，一个一个判断，利用"FILO"的方式进行表示，所以就有了如下的思路： ================================================================================================== 1.将元素一个一个压栈，若将要入栈的元素和栈顶元素匹配，那么弹出栈顶元素。 2.遍历整个字符串，当遍历完了以后，判断当前栈底，栈顶都在哪里。如果相等，说明匹配，否则。 ======================================================================= 为什么要遍历完?这是一个问题！！为什么不能再中途引进错误判断机制呢？所以，就有了如下的思考： 将这些匹配元素，我们可以分为两类： 一类为左，一类为右。（这不是废话吗？） 书面一点：一类为起始符，一类为结束符。 规则是这样的： ================================================ 有了起始符，才会出现结束符！ ================================================ 但检测到将入栈的元素和栈顶元素不为同一类，并且不匹配。那么，我们就有权去说：不用查了，这个字符串打死我，我也会说No. 如果说，栈操作深奥了，可以利用外部数组（就是数组）的方式来作为删除元素的缓存Buff。 那么，就有了如下的思考： =============================================================================================== 1.判断当前字符串的长度。 2.将字符串从第一个字符拷贝到Buff中。 3.错误判断机制，若在不同类，并且匹配，那么将当前所在的索引处的值初始化，并将数组元素的动态索引值-1. 4.期间，没有错误，并且处理完当前字符串，否则No. 5.ok，没有问题，返回YES。 ===================================================================================== 以上，只是解决了字符串的匹配问题，还有输出呈现问题。 输出呈现，是全部遍历完成字符串数组以后，然后再输出的，所以需要有一个缓存Buff，存储当前结果是YES or No。 =============================================================== 最简单的，就算是用for循环遍历这个数组了，0为No，1为YES. =============================================================== 好的，已经解决了提设的问题，但是，想想该问题还是简单化了！ =====================================================================================
- 如果是3对匹配，4对匹配呢？
- 是否需要考虑封装的问题？将匹配函数封装，满足支持动态扩展的形式进行扩展，而不是固定匹配()和[].
- 如果中间存在其他值，而不是单独的字符，该如何处理？忽略掉非匹配字符类？然后按照类似的方法进行。
- …………其他
=================================================================================================
以上，便是思考的全部过程，有错误，有修正，觉得对思考有帮助，便记录下来。
以下便是代码了，相信0基础的童鞋应该都可以看懂吧。
1 #include
2 #include 3 4 int Judge_Sts(char* str,int length); 5 int Judge_Type(char Name); 6 int Match_Char(char Start,char End); 7 8 int main(void) 9 { 10 /*局部变量定义*/ 11 int Num; 12 int Index; 13 int Str_Length; 14 char Temp[10000]; 15 char OutFlag[100]; 16 char bflag; 17 /* 获取行数 */ 18 scanf("%d",&Num); 19 /* 循环处理 */ 20 for(Index = 0;Index < Num; Index++) 21 { 22 scanf("%s",&Temp); 23 /* 判断长度 */ 24 Str_Length = strlen(Temp); 25 /* 奇数 */ 26 if(Str_Length&1) 27 { 28 OutFlag[Index] = 0; 29 } 30 else 31 { 32 /* 偶数就开始判断 */ 33 OutFlag[Index] = Judge_Sts(Temp,Str_Length); 34 } 35 } 36 /* 输出YES or NO */ 37 for(Index = 0; Index < Num; Index++) 38 { 39 if(OutFlag[Index]) 40 { 41 printf("YES\n"); 42 } 43 else 44 { 45 printf("NO\n"); 46 } 47 } 48 } 49 50 /* 判断字符串 */ 51 /* 52 * 不匹配：0 53 * 匹配：1 54 */ 55 int Judge_Sts(char* str,int length) 56 { 57 int i; 58 char* TagStr = NULL; 59 int Bret = 1; 60 char Temp; 61 int Str_Top = 0; 62 63 TagStr = str; 64 for(i = 0; i < length; i++) 65 { 66 Temp = *(str+i); 67 if(Judge_Type(Temp)) 68 { 69 if(Str_Top == 0) 70 { 71 Bret = 0; 72 break; 73 } 74 else 75 { 76 Str_Top--; 77 if(Match_Char(*(TagStr+Str_Top),Temp)) 78 { 79 ; 80 } 81 else 82 { 83 Bret = 0; 84 break; 85 } 86 } 87 } 88 else 89 { 90 *(TagStr+Str_Top) = *(str+i); 91 Str_Top++; 92 } 93 } 94 95 if(Str_Top) 96 { 97 Bret = 0; 98 } 99 else100 {101 Bret &= 1;102 }103 return (Bret);104 }105 106 /* 判断该字符属于哪一种，开始字符 or 结束字符 */107 /*108 * 开始符：0 109 * 结束符：1 110 */ 111 int Judge_Type(char Name)112 {113 int bRet = 1;//默认需要和前一个判断 114 switch(Name)115 {116 case '(':117 case '[':118 bRet = 0;119 break;120 case ')':121 case ']':122 bRet = 1;123 break;124 default:125 break;126 }127 128 return (bRet);129 }130 131 /* 判断是否匹配 */132 int Match_Char(char Start,char End)133 {134 int a;135 if((Start == '(' && End == ')') || (Start == '[' && End == ']') )136 {137 a = 1;138 }139 else140 {141 a = 0;142 }143 return a;144 } （PS:有时间在想出一些巧妙的方法出来吧。先这样了。）