括号匹配.txt

这是有关数据结构的例程序

definition
===========================
#define INIT_SIZE 100 //存储空间初始分配量
#define INCREMENT 10  //存储空间分配增量

typedef char ElemType;

typedef struct{
ElemType *top, *base; //栈顶指针和栈底指针
unsigned stacksize;   //当前已分配的存储空间，以元素为单位
}SqStack;

int InitStack(SqStack *);//创建一个空栈
int Push(SqStack *, char);     //插入栈顶
int Pop(SqStack *);      //删除栈顶元素
=========================================================================

function.c
==================================================
#include<stdio.h>
#include<malloc.h>
#include"definition.h"

int InitStack(SqStack *S) //创建一个空栈
{ S->base=(ElemType *)malloc( INIT_SIZE * sizeof(ElemType) );
if(!S->base) //空间分配失败
  return 1;
//空间分配成功
S->top=S->base;//置栈顶指针
S->stacksize=INIT_SIZE;//栈大小
return 0;
}

int Push(SqStack *S, char e) //插入栈顶
{ if( (unsigned)(S->top - S->base) >= S->stacksize){//栈满，追加存储空间
  S->base=(ElemType *)realloc(S->base, (S->stacksize+INCREMENT)*sizeof

(ElemType) );
  if(!S->base)//分配失败，返回1
   return 1;
  //分配成功
  S->top = S->base + S->stacksize;//置栈顶指针
  S->stacksize += INCREMENT;//栈大小
}

*S->top++ = e; //接收输入后，S->top指向栈顶元素的下一个位置

return 0;
}

int Pop(SqStack *S) //删除栈顶元素
{ if(S->base == S->top)//空栈，返回0
  return 0;
return *( --(S->top) );//不空，栈顶指针下移（即删除栈顶元素），并且返回栈顶元素
} ============================================================================

main.c
==================================================
#include<stdio.h>
#include<malloc.h>
#include"definition.h"

int main()
{ SqStack S;
ElemType e;

if( InitStack(&S) ){
  printf("创建堆栈失败。\n");
  return 1;
}

do{
  printf("请输入“(、)、[ 或者 ]”中的任意一个：");
  e=getchar();
  getchar();
  if( e=='(' || e=='[' ) //左括号压栈
   Push(&S, e);
  else if( e==')' || e==']' ){//右括号判断
   if( (*(S.top-1)=='(' && e==')') || (*(S.top-1)=='[' && e==']') )
    Pop(&S);//匹配则出栈
   else{//不匹配则退出
    printf("匹配失败。\n");
    return 1;
   }
   
  }
  else{//输入不合法字符，退出
   printf("输入不合法。\n");
   return 1;
  }
}while(S.top != S.base);//S.top==S.base则说明匹配完成

printf("匹配成功。\n");
free(S.base);
return 0;
}