数据结构之括号匹配问题的解决

经过这几天的思索,终于完成了括号匹配问题算法的实现,不多说,把代码献出来,有问题请大家多指教

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #define STACK_INIT_SIZE 100
 4 #define STACKINCREMENT  10
 5 typedef char SElemType;
 6 
 7 typedef struct {
 8        SElemType   *base;  //栈底
 9        SElemType   *top;   //栈顶
10        int   stacksize;    //当前可用最大容量
11 }SqStack;
12 
13 void InitStack (SqStack &S){
14     S.base=(SElemType*)malloc(STACK_INIT_SIZE  *sizeof(SElemType));
15     if (!S.base) exit (0); //存储分配失败
16     S.top = S.base;
17     S.stacksize = STACK_INIT_SIZE;
18 }
19 
20 void Push (SqStack &S, SElemType e) {
21    if (S.top - S.base >= S.stacksize) {//栈满,追加存储空间
22       S.base = (SElemType *) realloc ( S.base,
23            (S.stacksize + STACKINCREMENT) * sizeof (SElemType));
24        if (!S.base) exit (0); //存储分配失败
25        S.top = S.base + S.stacksize;
26        S.stacksize += STACKINCREMENT;
27    }
28    *S.top=e;
29    S.top++;
30    
31  }
32 
33 
34 void Pop (SqStack &S, SElemType &e) {
35      // 若栈不空,则删除S的栈顶元素,
36      // 用e返回其值,并返回OK;
37      // 否则返回ERROR
38     if (S.top == S.base) exit(0);
39     
40     --S.top;
41     e=*S.top;
42 }
43 
44 
45 
46 void GetTop (SqStack S, SElemType &e) {
47 // 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
48     if (S.top == S.base) exit(0);
49     e = *(S.top-1);
50 }
51 
52 
53 void main( ){
54     SqStack s;
55     SElemType e,ch;
56     int flag=1;
57    InitStack(s);
58    ch=getchar();
59    while(ch!='#'&&flag){
60           switch(ch){
61             case'[': Push(s,ch);break;
62             case'(':Push(s,ch);break;
63             case ']' : 
64                 if(s.top !=s.base){
65                     GetTop(s,e);
66                     if(e='['){
67                     Pop(s,e);
68                     flag=1;
69                 }
70                 else flag=0;
71                 }
72                 else exit(0);
73                 break;
74             case ')' :
75                 if(s.top!=s.base){
76                     GetTop(s,e);
77                     if(e=='('){
78                     Pop(s,e);
79                     flag=1;
80                     }
81                 else flag=0;
82                 }
83                 else exit(0);
84                 break;
85 
86             default :break;  
87           }
88           scanf(" %c",&ch);
89          
90      }
91   if(flag==1)
92       printf("YES");
93   else printf("NO");
94 }
原文地址:https://www.cnblogs.com/yjh123/p/5997833.html