202319.cpp

数据结构（清华版）

#include<iostream.h>
#include <malloc.h>

typedef char SElemtype;
//建立顺序栈==================================================
struct SStack
{
	SElemtype *top,*base;
	int Stacksize;
};
//判断栈是否为空==============================================
bool StackEmpty(SStack S)
{
 return S.top==S.base;

}
//出栈
bool Pop(SStack &S,SElemtype &e)
{
	if(S.top==S.base) return false;
	S.top--;
	e=*S.top ;
	return true;
}
//构建栈函数===================================================
bool StackInit(SStack &S)
{
	S.base=new SElemtype[100];
	if(!S.base) return false;
	S.top=S.base;
	S.Stacksize=100;
	return true;
}
//入栈========================================================
bool Push(SStack &S,SElemtype e)
{
	SElemtype *newbase ;
	if(S.top-S.base==S.Stacksize)
	{
		newbase=(SElemtype*)realloc(S.base,(S.Stacksize+10)*sizeof(SElemtype));
		if(!newbase)return false;
		S.base=newbase;
		S.top=S.base+S.Stacksize;
		S.Stacksize+=10;
	}
	*(S.top)=e;
	S.top++;
}
//构建函数判别表达式中括号是否匹配========================
bool JYPP(char *a)
{
  SStack s;
  StackInit(s);
  SElemtype *p,e;
  for(p=a;p;p++)
  {
	if(*p=='('||*p=='['||*p=='{') Push(s,*p);//入栈
    else if(*p==')'||*p==']'||*p=='}')
    {
	  
      Pop(s,e);//出栈
      if(*p==')'&&e!='(') return false; //必须与当前栈顶括号匹配
      if(*p==']'&&e!='[') return false;
      if(*p=='}'&&e!='{') return false;
    }
	if(StackEmpty(s)) break;
  }
  return StackEmpty(s);
}


//主函数============================================
void main()
{
	SElemtype a[]={'{','[','[',']','}','}'};
	if(JYPP(a))  cout<<"括号匹配";
	else  cout<<"括号不匹配";

}