sqstack.cpp

括号匹配的检验 试写一个判别表达式开、闭括号是否配对出现的算法。

#include <stdlib.h>
#include "ds.h"
#include "SqStack.h"
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 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;
	return OK; 
}
///////////////////////////////////////////////////////////////
Status StackEmpty(SqStack S)
{
  return (S.top==S.base);
}
///////////////////////////////////////////////////////////////
int StackLength(SqStack S)
{
	return S.top-S.base;	
}
///////////////////////////////////////////////////////////////
Status GetTop(SqStack S,SElemType &e)
{
  if(S.top==S.base) return ERROR;
  e=*(S.top-1);
  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;
}
///////////////////////////////////////////////////////////////
Status StackTraverse(SqStack S,Status (*visit)(SElemType))
{
	SElemType *bp;
	bp=S.base;
	while(bp!=S.top)
		visit(*bp++);
	return OK;
}