栈的应用举例——括号匹配

例题：假设通过键盘输入的一个表达式中只出现()和[]并允许任意顺序的嵌套，设计算法，检测括号是否匹配。

思路：当读取到一个左括号时，将产生一个“匹配的意愿”，若再读取到一个左括号，又将产生一个“匹配的意愿”，且后读取到的比先读取到的“匹配的意愿更强烈” 

因此可借助栈，按“意愿强烈的优先级” 保存所有未匹配的左括号，即读到左括号即入栈。

当遇到右括号时，则从栈中弹出左括号，检验匹配情况。 

 ( ) [ ] 的ASCII码分别为40、41、91、93 

在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。 

1. 当遇到一个右括号时，栈已空，说明到目前为止，右括号多于左括号
2. 从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况
3. 算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号

#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define OVERFLOW -2
#define ERROR 0
typedef char SElemType;
typedef int Status;
typedef struct{
   SElemType  *base;
   SElemType  *top;
   int stacksize;
}SqStack;

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 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 StackEmpty(SqStack s)
{
  return s.top==s.base;
}


int main()
{
  char ch,e;
  SqStack s;

  InitStack(&s);
  //( 40 、 )41 、[ 91 、] 93

  while((ch=getchar())!='\n')
  {
     if(ch=='('||ch=='[')
       Push(&s,ch);
     else if(ch==')'||ch==']')
     {
       if(!StackEmpty(s))
       {
			Pop(&s,&e);
			if(!(ch-e==1||ch-e==2)){printf("error!!");exit(0);}
       }
       else
	   {
		   printf("error!");
		   exit(0);
	   }
    }
}
  if(!StackEmpty(s)) printf("error!");
  else printf("success!");
  
  return 0;
}

Status khpp() {
  char ch,e;
  SqStack s;
  InitStack(&s);
  //( 40 、 )41 、[ 91 、] 93
  while((ch=getchar())!='\n')
  {
     if(ch=='('||ch=='[')
       Push(&s,ch);
     else if(ch==')'||ch==']')
     {
       if(!StackEmpty(s))
       {
			Pop(&s,&e);
			if(!(ch-e==1||ch-e==2)){
			    printf("error!!");
				return 0;}
       }
       else
	   {
		   printf("error!");
		   return 0;
	   }
     }
  }
  if(!StackEmpty(s)) printf("error!");
  else printf("success!");
}