实验四：用栈检测括号的匹配（2学时）
本次实验的主要目的在于使学生深入了解栈的特性，以便在实际问题背景下灵活运用；同时还将巩固对这种结构的构造方法的理解。
（一） 问题描述
括号匹配问题是编译程序时经常遇到的问题，用以检测语法是否有错。
（二） 基本要求
1. 用顺序栈来检测括号是否匹配。
2. 令所给的式子中出现（）[ ]{ }这几种括号形式。
（三） 测试数据
自拟。务必涵盖以下情况:
1.个数不对,如( ( )
2. 个数不对,如 ( ) )
3.匹配不符,如( [ ) ]
（四） 实现提示
若为左半边括号则压栈，若为右半边括号，则与栈顶位置的括号比较是否匹配，若栈空,则表示一种不匹配的情况,若栈不空,则令栈顶元素出栈，若配不上，为不匹配的另一种情况；全部序列检测完毕后，看栈是否为空，若是，则匹配，否则，为不匹配的第三种情况。可设一标志变量flag，初值为true，若出现不匹配情况，令flag=false，最后对flag做一次检测，判断括号是否匹配。
本文代码在turbo C 2.0的环境下实现
用栈实现括号匹配的检验
代码一
//实验四：用栈实现括号匹配的检验#include<stdio.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 //函数结果状态代码#define NULL 0typedef int Status;
#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10
typedef char SElemType;typedef struct{ SElemType *base; SElemType *top; int stacksize;}SqStack;Status InitStack(SqStack *s){s->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType)); if(!s->base) exit(OVERFLOW); s->top=s->base; s->stacksize=STACK_INIT_SIZE; return OK;}Status Push(SqStack *s,SElemType e){if(s->top-s->base>s->stacksize){ s->base=(SElemType *)realloc(s->base,(s->stacksize+STACKINCREMENT) *sizeof(SElemType)); if(!s->base) exit(OVERFLOW); s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT; } *s->top++=e; return OK;}Status Pop(SqStack *s,SElemType *e){ if(s->top==s->base) return ERROR; *e=*--s->top; return OK;}SElemType GetTop(SqStack S){SElemType e; e=*(S.top-1); return e;}Status StackEmpty(SqStack *s){ if(s->top==s->base) return TRUE; else return FALSE;}Status DestroyStack(SqStack *s){ free(s->base);s->base=NULL; s->top=NULL; s->stacksize=0; return OK;}Status ClearStack(SqStack *s){s->top=s->base; s->stacksize=STACK_INIT_SIZE; return OK;}main(){ int i=0;int flag=1; SElemType elem,*e; char ch; char B[50]; SqStack S,*s; s=&S; e=&elem; do{ scanf("%c",&ch); B[i]=ch;i++; }while(ch!='@'); InitStack(s); i=0;ch=B[i]; while(ch!='@'&&flag){ if(ch=='('||ch=='[') Push(s,ch); if(ch==')'){ if(!StackEmpty(s)){ Pop(s,e); if(elem!='(') flag=0; } else flag=0; } if(ch==']'){ if(!StackEmpty(s)){ Pop(s,e); if(elem!='[') flag=0; } else flag=0; } i++; ch=B[i]; } if(!StackEmpty(s)) flag=0; if(flag) printf("MATCH/n"); else printf("Not MATCH/n"); DestroyStack(s); getch();}
代码二 更少变量实现一样的功能
//kuohao pipei de jianyan
#include<stdio.h>#define OVERFLOW -1#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define NULL 0typedef char SElemType;typedef int Status;typedef struct{ SElemType *top; SElemType *base; int stacksize;}SqStack;Status InitStack(SqStack *S){ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); //开辟空间 if(!(*S).base) exit(OVERFLOW); //存储分配失败 else { (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK; }}
Status DestroyStack(SqStack *S) //销毁栈{ free((*S).base); (*S).base=NULL; (*S).top=NULL; (*S).stacksize=0; return OK;}
Status StackEmpty(SqStack *S){ if((*S).top==(*S).base) return OK; else return ERROR;}Status Push(SqStack *S,SElemType e) //插入为新的栈顶元素
{ if((*S).top-(*S).base>=(*S).stacksize) //栈满 追加存储空间{(*S).base=(SElemType *)realloc((*S).base, ((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW); //储存分配失败 (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; } *(*S).top=e; (*S).top++; return OK;}
Status Pop(SqStack *S,SElemType *e){ if((*S).top==(*S).base) return ERROR; else { (*S).top--; e=*((*S).top); return OK;} }
main(){ SqStack S; SElemType elem; char e,a[20]; int i=0; int flag=1; clrscr(); printf("input the kuohao (<=20 ge) and press '#' to show the end:/n"); do{ scanf("%c",&e); a[i]=e; i++; }while(e!='#'); if( InitStack(&S))printf("kongjian yijing zhunbei hao!/n"); else printf("there is not enough room!/n"); i=0;e=a[i]; printf("kuohao yijing chenggong cunchu!/n"); //将括号存入空间
while(e=='#'&&flag) { switch(e) {case '(': case '[': case '{': Push(&S,e); i++;e=a[i]; break; //左括号入栈
case ')':if(!StackEmpty(&S)) {Pop(&S,e); //右括号 匹配的话 出栈 if(e!='(')flag=0; } else flag=0; i++;e=a[i]; break; case ']': if(!StackEmpty(&S)) { Pop(&S,e); if(e!='[') flag=0; } else flag=0; i++;e=a[i]; break; case '}':if(!StackEmpty(&S)) { Pop(&S,e); if(e!='{') flag=0; } else flag=0; i++;e=a[i]; break; } } if(!StackEmpty(&S)) flag=0; if(flag==1)printf("MATCH!/n"); else printf("MIS MATCH!/n"); if(DestroyStack(&S))printf("the stack is already destroyed!/n"); else printf("cannot destroy!"); getch();}
