match.cpp

检验括号是否匹配可以用堆栈来实现

#include <stdio.h>
#include <malloc.h>

//定义顺序堆栈
#define STACK_SIZE 100
#define STACK_INC 10

#define Maxsize 100

typedef char Elem;

typedef struct{
     Elem *base;
     Elem *top;
     int size;
   }SqStack;


/*创建空堆栈*/
int  InitStack(SqStack &S)
{
    S.base=(Elem *)malloc(STACK_SIZE*sizeof(Elem));
    S.top=S.base;
    S.size=STACK_SIZE;
    return 1;
}

/*堆栈是否为空*/
int StackEmpty(SqStack S)
{
    if(S.top!=S.base) return 0;
    return 1;
}

/*进栈*/
int Push(SqStack &S,Elem e)
{
    if(S.top-S.base>=S.size)
    {
        S.base=(Elem *)realloc(S.base,(S.size+STACK_INC)*sizeof(Elem));
         S.top=S.base+S.size;
         S.size+=STACK_INC;
     }
     
    *S.top=e;
    S.top+=1;
    return 1;
}

/*出栈*/
int Pop(SqStack &S,Elem &e)
{
    if(S.top==S.base) return 0;
    S.top-=1;
    e=*S.top;
    return 1;
}

//括号匹配
int BracketMatch(SqStack &S,char *str)
{
  int i;        //定义字符串的控制变量
  int state;  //定义状态控制变量
  int state2;
  
  int priory;   //定义优先级变量
  
  Elem e;
  
  i = 0;
  state = 0;
  priory = 4;
  
  while(str[i]!='\0')
  {
      switch(str[i])
      {
       case '(': if(priory > 1)
                {
                    Push(S,'(');
                    priory =1;
                }
                else return 0;
                break;
       case '[':if(priory > 2)
                {
                   Push(S,'[');
                    priory =2;
                }
                else return 0;
                break;
       case '{':if(priory > 3)
                {
                   Push(S,'{');
                    priory =3;
                }
                else return 0;
                break;
                
      case ')':{Pop(S,e);
                if(e!='(') state=1; break;}
      case ']':{Pop(S,e);
                if(e!='[') state=1;break;}
      case '}':{Pop(S,e);
                if(e!='{') state=1;break;}
      default: break;
    }//switch
    
    if(state) break; //出现不匹配，立即结束循环
    
    i++;
  }//while
  
  state2=StackEmpty(S); //flag2判断堆栈是否为空
  
  if(!state && state2)  return 1;   //匹配，返回1
  else return 0;        //不匹配，返回0
}

//主函数
void main()
{
    int match;
    char str[Maxsize];
    char temp;
  
    SqStack S;
    InitStack(S);
    
    printf("input the string:");
    scanf("%s",str);
    //scanf("%c",&temp); //接受输入的回车键
    
    match = BracketMatch(S,str);
    
    if(match==1)
    {
        printf("*****The string match!*****\n");
    }
    else printf("*****The string don't match!*****\n");

}