数据结构-括号匹配程序

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 #define STACK_INIT_SIZE 100
 5 #define STACKINCREMENT 10
 6 #define OVERFLOW -2
 7 #define OK 1
 8 #define ERROR 0
 9 
10 typedef char SElemType;
11 
12 //栈结构体
13 typedef struct {
14     SElemType *base;
15     SElemType *top;
16     int stacksize;
17 }SqStack;
18 
19 int InitStack(SqStack *S);//初始化栈
20 int Push(SqStack *S,SElemType e);//入栈
21 int Pop(SqStack *S,SElemType *e);//删除栈中的元素
22 int DestoryStack(SqStack *S);//销毁栈
23 
24 //初始化栈
25 int InitStack(SqStack *S) {
26     S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
27     if(!S->base) {
28         exit(OVERFLOW);
29     }
30     S->top = S->base;
31     S->stacksize = STACK_INIT_SIZE;
32 
33     return OK;
34 }
35 
36 //入栈
37 int Push(SqStack *S,SElemType e) {
38     if((S->top-S->base)>=S->stacksize) {
39         S->base = (SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
40         if(!S->base) exit(OVERFLOW);
41         S->top = S->base + S->stacksize;
42         S->stacksize += STACKINCREMENT;
43     }
44     *S->top++ = e;
45     return OK;
46 }
47 
48 //删除栈中的元素
49 int Pop(SqStack *S,SElemType *e) {
50     if(S->top  == S->base) return ERROR;
51     *e = *--S->top;
52     return OK;
53 }
54 
55 //销毁栈
56 int DestoryStack(SqStack *S) {
57     S->top = S->base;
58     free(S->base);
59     S->top = NULL;
60     S->base = NULL;
61     return OK;
62 }
63 
64 //进行括号匹配
65 int Match(SqStack *S) {
66     char ch,c;
67     InitStack(S);
68     ch = getchar();
69     while(ch != ‘\n‘) {
70         if(ch==‘(‘||ch==‘[‘) {
71             Push(S,ch);
72         }
73         if(ch==‘)‘) {
74             Pop(S,&c);
75             if(c!=‘(‘) {
76                 return ERROR;
77             }
78         }
79         if(ch==‘]‘) {
80             Pop(S,&c);
81             if(c!=‘[‘) {
82                 return ERROR;
83             }
84         }
85         ch = getchar();
86     }
87     return OK;
88 }
89 
90 int main()
91 {
92     SqStack *sq;
93     int f;
94     f = Match(sq);//进行括号匹配检验
95     if(f) printf("括号全部匹配！\n");
96     else printf("括号匹配失败！\n");
97     DestoryStack(sq);//将栈销毁
98     return 0;
99 }