验证括号的匹配 实验报告

深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时巩固对这两种结构的构造方法的理解。

二、实验环境

硬件：计算机   软件：Microsoft Visual C++

三、实验内容    

利用栈（以顺序栈作存储结构）实现括号匹配的检验。

四、实验程序

#include

#include

#define TRUE 1

#define FALSE 0

#define STACK_INIT_SIZE 50

#define STACKINCREMENT 5

typedef int Status;

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)return(FALSE);

 s.top=s.base;

 s.stacksize=STACK_INIT_SIZE;

 return TRUE;

}

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)

   return(FALSE);

  s.top=s.base+s.stacksize;

  s.stacksize+=STACKINCREMENT;

 } 

 *s.top++=e;

    return TRUE;

}

Status Pop(SqStack &s,SElemType &e){

 if(s.top==s.base){

 return FALSE;}

   e=*--s.top;

    return TRUE;

}

Status Cmp(SElemType &e,char ch){

 if((e=='(')&&(ch==')')) return TRUE;

 else if((e=='[')&&(ch==']')) return TRUE;

 else if((e=='{')&&(ch=='}')) return TRUE;

 return FALSE;

}

Status check()

 { SqStack s; InitStack(s); SElemType ch,e;

       while ((ch=getchar( ))!='\\n') 

         if (ch=='('||ch=='['||ch=='{')   Push(s,ch); 

           else  if (ch==')'||ch==']'||ch=='}')

           {  if (!Pop(s,e)) return FALSE; 

              if (!Cmp(e, ch)) return FALSE; 

           }

       if (s.top==s.base)  return  TRUE;

        return FALSE;

}

void main(){

 SqStack s;

InitStack(s);

if(check()) printf("括号匹配");

else  printf("括号不匹配");

}

五，实验结果