括号匹配要求:括号要成对匹配,不能有交叉,如(({}[]()))是合适的,(([])和{([]})是不匹配的

算法描述:

假设有一个字符串str,其中包含有"(",")","{","}","[","]","<",">"这样的字符,或没有.

1.设置一个空栈.

2.对字符串中每一个字符做如下操作:

2.1 如果字符为左括号:

如果栈满,则返回栈空间不够的错误.

否则,将字符压栈;

重复操作(操作下一个字符);

2.2 如果字符为右括号,则查看当前栈顶的字符是否和此字符匹配:

如果匹配

栈顶元素弹出,操作下一个字符,跳到2

否则,括号不匹配,返回不匹配

2.3其他字符,则操作下一个字符

3.查看栈是否为空:

如果栈空,返回匹配

否则,返回不匹配,并指出"缺少右括号"

用C语言来写就是这样:

 1 #include <stdio.h>
 2 #define SIZE    1024
 3 #define is_left(c)  (((c)=='(')||((c)=='{')||((c)=='[')||((c)=='<'))
 4 #define is_right(c) (((c)==')')||((c)=='}')||((c)==']')||((c)=='>'))
 5 /**
 6  * this macro is_pair assumes that l is the left,
 7  * and it is only used by myself.:-)
 8  */
 9 #define is_pair(l,r)    ((l)=='('?(r)==')':(r)==(l)+2)
10 
11 #define  ERR_NO_LEFT        1
12 #define  ERR_NO_RIGHT       2
13 #define  ERR_CROSS          3
14 #define  ERR_TOO_LONG       4
15 #define  ERR_NULL_STRING    5
16 
17 int
18 test_pair(const char *str){
19     char stack[SIZE];
20     int top=-1;
21 
22     if(!str){
23         return -ERR_NULL_STRING;
24     }
25     while((*str)!='\0'){
26         if(is_left(*str)){
27             if(top>SIZE-2){
28                 return -ERR_TOO_LONG;
29             }
30             stack[++top]=*str;
31             str++;
32             continue;
33         }
34         if(is_right(*str)){
35             if(is_pair(stack[top],*str)&&top>=0){
36                 top--;
37                 str++;
38                 continue;
39             }
40             return (top<0 ? -ERR_NO_LEFT : -ERR_CROSS);
41         }
42         str++;
43     }
44     return (top>=0 ? -ERR_NO_RIGHT : 0);
45 }