#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

#define OK 1
#define ERROR -1
#define OVERFLOW -1
#define ENDFLAG 0
typedef int Status;
typedef int SElemType;

#define STACK_INIT_SIZE 100     
#define STACLINCREMENT 10

typedef struct{
	SElemType  *base;     /*栈的基地址*/
	SElemType  *top;	  /*栈顶指针*/
	int stacksize;
}SqStack;//顺序栈

Status InitStack(SqStack *S)//构造一个空的栈
{
	S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));//malloc申请动态内存的专用函数
	if(!S->base)
	{
		printf("/nOut of space./n");
		getch();
		exit(OVERFLOW);/*溢出*/
	}
	S->top=S->base;
	S->stacksize=STACK_INIT_SIZE;
	return OK;
}
Status push (SqStack *S,SElemType e)
{ 
	if(S->top-S->base>=S->stacksize)
	{	
		S->base=(SElemType *)realloc(S->base,(S->stacksize+STACLINCREMENT)*sizeof(SElemType));
		//realloc 可以对给定的指针所指的空间进行扩大或者缩小，原有内存的中内容将保持不变
		if(!S->base)
		{	printf("\nOut of space.\n");
		getch();
		exit(OVERFLOW);
		}
		S->top=S->base+S->stacksize;
		S->stacksize+=STACLINCREMENT;
	}
	*S->top++=e;
	return OK;
}
Status pop(SqStack *S,SElemType *e)
{
	if(S->top==S->base)
	{
		printf("\nThe stack is empty.\n");
		return ERROR;
	}
	*e=*--S->top;
	return OK;
}


void match(char str[])
{
	SqStack S;
	char *p;
	SElemType e;
	InitStack(&S);
	p=str;
	while (*p)
	{
		if (*p=='('||*p=='['||*p=='{')push(&S,*p);
		else if(*p==')'||*p==']'||*p=='}')
		{


			if (*(S.top-1)+1==*p||*(S.top-1)+2==*p )
		pop(&S,&e);
			else{
				printf("\nMismatch.\n");
				return;
			}
		}
		p++;
	}
	if(S.top==S.base)
		printf("\nMatch.\n");
	else
		printf("\nMisamatch.\n");
}
void main (void)
{	
	char str[100];
	printf("\nInput the expression:\n");
	gets(str);
	match(str);
	getch();
}
//if (*(S.top-1)+1==*p||*(S.top-1)+2==*p )是什么意思