202319.cpp

数据结构（清华版）

#include<iostream.h>
#include <malloc.h>
typedef char Elemtype;
//构建结构体=================================================
struct SList
{
	Elemtype *elem;
	int length,listsize;
};

//创建线性表
bool ListCreate(SList  &L,int n,Elemtype a[])
{
	int i;
	L.elem=new Elemtype[n+100];
	if(!L.elem) return false;
	L.length=n;
	L.listsize=n+100;
	for(i=0;i<n;i++) L.elem[i]=a[i];
	return true;
	
}

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(SList x)
{
  SStack s;
  int i;char c,e;
  StackInit(s);
  for(i=0;i<x.length;i++)
  {   c=x.elem[i];
	  if(c=='('||c=='['||c=='{') {Push(s,c);}//入栈
	  else if(c==']')
	  {if (!Pop(s,e)||e!='[')return false; }
      else if(c==')')
	  {if (!Pop(s,e)||e!='(') return false;}
	 
	  else if(c=='}')
	  {if (!Pop(s,e)||e!='{') return false;}

      /*if(*p==')'&&e=='(') return true; //必须与当前栈顶括号匹配
      else if(*p==']'&&e=='[') return true;
      else if(*p=='}'&&e=='{') return true;
	  else return false;*/
  }
  return StackEmpty(s);
}


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

}