栈的应用之括号匹配的检验

书本说到，栈的一个应用就是括号匹配的检验（P49），今天小弟兴致来了，想把它实现之，之中大部分代码是书本上的，小弟只是把它C++中引用的思想改成了我们的C的指针，还完成了检验的功能，有错的就请大家指出来，有更好的，希望可以跟小弟分享

编译器VC6.0，系统windows XP

stack.h
stack.h

1 #include <stdio.h> 2 #include <malloc.h> 3 #include <stdlib.h> 4  5  #define TRUE             1 6  #define FALSE            0 7  #define OK               1 8 #define ERROR            0 9 #define INFEASIBLE       -110 #define OVERFLOW         -211 #define STACK_INIT_SIZE  10012 #define STACKINCREMENT   1013 14 typedef char SElemType;15 typedef int Status;16 17 typedef struct18 {19     SElemType *base;20     SElemType *top;21     int stacksize;22 }SqStack;23 24 Status InitStack (SqStack *S);//构造一个空栈25 Status DestroyStack (SqStack *S);//销毁栈S26 Status ClearStack (SqStack *S);//把S置为空栈27 Status IsEmpty (SqStack S);//判断S是否为空28 int StackLength (SqStack S);//测量S的长度29 Status GetTop (SqStack S, SElemType *e);//获得S的栈顶元素30 Status Push (SqStack *S, SElemType e);//进栈31 Status Pop (SqStack *S, SElemType *e);//出栈，e为出栈元素的值32 Status IsEqual(SqStack S,SElemType e);//判断与栈顶元素是否匹配33 void Print(SqStack S);//打印栈的内容

stack.c

stack.c

1 #include "stack.h"  2 Status InitStack (SqStack *S)  3 {  4     //构造一个空栈S  5     S->base = (SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType));  6     if (!S->base) exit (OVERFLOW);  7     S->top = S->base;  8     S->stacksize = STACK_INIT_SIZE;  9     return OK; 10 }//InitStack 11  12 Status DestroyStack (SqStack *S) 13 { 14     //销毁S 15     free(S); 16     return OK; 17 } 18  19 Status ClearStack (SqStack *S) 20 { 21     //把S置为空栈 22     S->top = S->base; 23     return OK; 24 } 25  26 Status IsEmpty (SqStack S) 27 { 28     //判空 29     if(S.base == S.top) 30         return TRUE; 31     else return FALSE; 32 } 33  34 int StackLength (SqStack S) 35 { 36     //测定S的长度 37     return (S.top - S.base)/sizeof(SElemType); 38 } 39  40 Status GetTop (SqStack S, SElemType *e) 41 { 42     //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR 43     if (IsEmpty(S)) return ERROR; 44     *e = * (S.top - 1); 45     return OK; 46 }//GetTop 47  48 Status Push (SqStack *S, SElemType e) 49 { 50     //插入元素e为新的栈顶元素 51     if (S->top - S->base >= S->stacksize) 52     { 53         //栈满，追加存储空间 54         S->base = (SElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT) * sizeof(SElemType)); 55         if(!S->base) exit(OVERFLOW);//存储分配失败 56         S->top = S->base + S->stacksize; 57         S->stacksize += STACKINCREMENT; 58     } 59     *(S->top++) = e; 60     return OK; 61 }//Push 62  63 Status Pop (SqStack *S, SElemType *e) 64 { 65     //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR 66     if(S->top == S->base) return ERROR; 67     *e = * (-- (S->top)); 68     return OK; 69 }//Pop 70  71 Status IsEqual(SqStack S,SElemType e) 72 { 73     //判断e是否和栈顶元素相等 74     SElemType elem; 75     if(!IsEmpty(S)) 76         GetTop(S, &elem); 77     else return FALSE; 78     switch(elem) 79     { 80     case '(': 81         if(')' == e) return TRUE; 82         else return FALSE; 83         break; 84     case '[': 85         if(']' == e) return TRUE; 86         else return FALSE; 87         break; 88     case '{': 89         if('}' == e) return TRUE; 90         else return FALSE; 91         break; 92     default: 93         return FALSE; 94         break; 95     } 96 }//IsEqual 97  98 void Print(SqStack S) 99 {100     SqStack stack = S;101     SElemType elem;102     while(!IsEmpty(stack))103     {104         Pop(&stack, &elem);105         putchar(elem);106     }107     putchar(10);108 }

main.c

main.c

1 #include "stack.h" 2 int main() 3 { 4      SqStack stack; 5      SElemType s[100]; 6      InitStack(&stack); 7      while(gets(s)) 8      { 9          char *p = s;10          for(; *p; p++)11          {12          if(IsEmpty(stack) || !IsEqual(stack, *p))13              Push(&stack, *p);14          else Pop(&stack, p);15          }16          if(IsEmpty(stack)) puts("Yes!");17           else puts("No!");18      }19      20      return 0;21 }

718
原文链接: https://www.cnblogs.com/gdut08network/archive/2010/03/08/1680985.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍