数据结构_括号匹配

          输入一串括号，检验括号是否匹配。

      　例如，考虑下列括号序列：

[ ( [ ] [ ] ) ]

　　1 2 3 4 5 6 7 8

当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号“[”只能暂时靠边，而迫切等待与第二个括号相匹配的、第七个括号“)”的出现，类似地，因等来的是第三个括号“[”，其期待匹配的程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号之后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配就成为当前最急迫的任务了，……依此类推。

很显然，这样的一个处理过程和栈的特点非常吻合，因此，这个问题可以用栈来解决。

解决思路：

　　1.在算法中设置一个栈，每次读入一个括号；

　　2.若是右括号，则或者使置于栈顶的最急迫的期待得以消解，此时将栈顶的左括号弹出；或者是不合法的情况，此时将右括号压入；

　　3.若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降低一级；

　　4.在算法的开始和结束时，栈应该为空。

 Status MatchCheck(SqList exp)

 2 /* 顺序表exp表示表达式；                        */

 3 /* 若exp中的括号配对，则返回TRUE，否则返回FALSE */

 4 {

 5     Stack s;

 6     char e;

 7 

 8     //逐个读入括号

9 for(int i=0;i10     {

11         if(exp.elem[i]=='('||exp.elem[i]=='{'||exp.elem[i]=='[')//若遇左括号，则直接入栈

12         {            

13             Push(s,exp.elem[i]);

14         }

15         else if(exp.elem[i]==')')//若遇右圆括号，则尝试匹配栈顶括号

16         {            

17             if(GetTop(s,e))

18             {

19                 if(e=='(')//匹配成功，左圆括号出栈

20                 {

21                     Pop(s,e);

22                 }      

23                 else//匹配不成功，右圆括号入栈

24                 {

25                     Push(s,exp.elem[i]);

26                 }          

27             }  

28             else//栈为空，则将右括号入栈

29             {

30                 Push(s,exp.elem[i]);                

31             } 

32         }

33         else if(exp.elem[i]=='}')//若遇右花括号，则尝试匹配栈顶括号

34         {

35             if(GetTop(s,e))

36             {

37                 if(e=='{')//匹配成功，左花括号出栈

38                 {

39                     Pop(s,e);

40                 }      

41                 else//匹配不成功，右花括号入栈

42                 {

43                     Push(s,exp.elem[i]);

44                 }          

45             }

46             else

47             {

48                 Push(s,exp.elem[i]);

49             } 

50         }

51         else if(exp.elem[i]==']')//若遇右方括号，则尝试匹配栈顶括号

52         {

53             if(GetTop(s,e))

54             {

55                 if(e=='[')//匹配成功，左方括号出栈

56                 {

57                     Pop(s,e);

58                 }      

59                 else//匹配不成功，右方括号入栈

60                 {

61                     Push(s,exp.elem[i]);

62                 }          

63             }

             else

65             {

66                 Push(s,exp.elem[i]);

67             } 

68         }

69     }    

70     if(StackEmpty(s))//当所有括号匹配成功时，栈应为空

71     {

72         return TRUE;

73     }

74     else

75     {

76         return FALSE;

77     }

78 }

（{}）

   匹配成功！ 

    匹配成功！

   通过这次实验，学会了如何做好一个操作性比较强的实验。有清晰的设计思路，良好的设计方案。

教师签字：　　　　　　    　年　　月　　日