數據結構之---C語言實現括號匹配（棧實現）

數據結構之---C語言實現括號匹配（棧實現）

#include 
#include 
#define STACKINCREAMENT 10
#define STACK_INIT_SIZE 100
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef int status;
typedef char SElemtype;
typedef struct
{
	SElemtype *base;
	SElemtype *top;
	status stacksize;
}sqstack;

//初始化棧
status Init(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 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 + STACKINCREAMENT) * sizeof(SElemtype));
	  if(!s->base)
			  exit(OVERFLOW);
      s->top = s->base + s->stacksize;
	  s->stacksize += STACKINCREAMENT;
	}
	*s->top++ = e;
	return OK;
}

//出棧
status pop(sqstack *s, SElemtype *e)
{
		if(s->top == s->base) 
				return ERROR;
		*e=*--s->top;
		return OK;
}

//判斷是否為空棧
status stackempty(sqstack *s)
{
		if(s->top==s->base)
			return OK;
		return ERROR;
}

//清空棧
status clearstack(sqstack *s)
{
		if(s->top == s->base) 
				return ERROR;
		s->top = s->base;
		return OK;
}

//括號匹配算法
status Parenthesis_match(sqstack *s,char *str)
{
		int i=0, flag=0;
		SElemtype e;
		while(str[i] != '')
		{
			switch(str[i])
			{
				case '(':
						push(s,str[i]);
						break;
				case '[':
						push(s,str[i]);
						break;
				case ')':
						{
						  pop(s,&e);
						  if(e != '(') 
								  flag=1;
						}
						break;
				case ']':
						{
						  pop(s,&e);
						  if(e!='[')
								  flag=1;
						}
						break;
				default:
						break;
			}
			if(flag)
					break;
			i++;
	}

   if(!flag && stackempty(s))
   		printf(括號匹配成功!
);
   else
   		printf(括號匹配失敗!
);
   return OK;
}

int main()
{
	char str[100], enter;
	sqstack s;
	Init(&s);
	printf(請輸入字符串:
);
	scanf(%s,str);
	scanf(%c,&enter);
	Parenthesis_match(&s,str);
    return 0;
}