数据结构括号匹配

╰+哭是因爲堅強的太久メ 2022-05-15 19:04 156阅读 0赞

三种括号形式( ),\[ \],\{ \},输入一段字符串，判断其括号是否匹配。

代码如下：

/*括号匹配问题*/
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define stack_init_size 100
    #define stackincrement 10
    #define error 0
    #define true 1
    #define false 0
    #define overflow -2
    #define ok   1
    
    typedef int Status;
    typedef struct
    {
            char *base;
            char *top;
            int stacksize;
    }SqStack;
    /*初始化栈函数*/
    Status Initstack(SqStack&s)
    {
         s.base=(char*)malloc(stack_init_size*sizeof(char));
         if(!s.base)
             exit(overflow);
         s.top=s.base;
         s.stacksize=0;
         return ok;
    }
    
    /*入栈函数*/
    Status Push(SqStack &s,char c)
    {
        if(s.top-s.base>=s.stacksize)
        {
            s.base=(char*)realloc(s.base,(s.stacksize+stackincrement)*sizeof(char));
            if(!s.base)
               exit(overflow);
            s.top=s.base+s.stacksize;
            s.stacksize+=stackincrement;
        }
        *(s.top)=c;
        (s.top)++;
        return ok;
    }
    /*出栈函数*/
    Status Pop(SqStack &s)
    {
           if(s.top==s.base)
             return error;
            s.top--;
           return ok;
    }
    /*判断非空函数*/
    Status StackEmpty(SqStack &s) 
    {
           if(s.top==s.base)
             return true;
            else
              return false;
    }
    
    /*取栈顶元素*/
    Status Gettop(SqStack &s,char &c)
    {
           if(s.top==s.base)
               return error;
           c=*(s.top-1);
           return ok;
    }        
    
    /*检测匹配函数*/
    Status CheckBrackts(char *expr)
    {       
            SqStack s;int i;char c;
            Initstack(s);
           for(i=0;expr[i]!='\0';i++)
           {
                                    
              if(expr[i]=='('||expr[i]=='['||expr[i]=='{')
                Push(s,expr[i]);
              else
                  if(expr[i]==')'||expr[i]==']'||expr[i]=='}')
                  {
                     if(StackEmpty(s))
                          return  error; 
                     else{
                          Gettop(s,c);
                          switch(expr[i]){
                              case ')':if(c!='(')
                                         return error;  break;
                              case ']':if(c!='[')
                                         return error;  break;
                              case '}':if(c!='{')
                                         return error;  break;
                                         }//switch
                           Pop(s);
                          }//if-else
           
                   }//if
            }//for
            if(StackEmpty(s))
               {return ok;
               printf("abc\n");}
            else
             return error;
     }          
     
     /*主函数*/ 
     int main()
     {
           int result;
           char b[100];
           char *a=b;
           gets(b);
           //printf("%s\n",a);
           result=CheckBrackts(a);
           if(result==1)
            printf("yes");
           else
            printf("no");
            system("pause");
            return 0;
    }