数据结构括号匹配问题（栈 C语言）

男娘i 2023-10-17 16:16 29阅读 0赞

现在，有一行括号序列，请你检查这行括号是否配对。

输入

数据保证只含有"\[","\]","(",")"四种字符

输出

如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No

代码如下

#include<stdio.h>
    #include<stdlib.h>
    #define SIZE 20
    #define CREMENT 10
    
    
    typedef struct{
    char *base;
    int top;
    int stacksize;
    }SqStack;
    
    
    //初始化 
    void InitStack(SqStack &S){
    S.base=(char *)malloc(SIZE*sizeof(char));
    if(!S.base) return ;
    S.top=0;
    S.stacksize=SIZE;
    }
    
    
    //判空 
    int StackEmpty(SqStack &S){
    if(S.top==0) return 1;
    else return 0;
    } 
    
    
    //入栈 
    void Push(SqStack &S,char e){
    if(S.top>=S.stacksize){
    S.base=(char *)realloc(S.base,(S.stacksize+CREMENT)*sizeof(char));
    if(!S.base) exit(0);
    S.stacksize+=CREMENT;
    }
    S.base[S.top++]=e;
    }
    
    
    //出栈 
    void Pop(SqStack &S,char &e){
    if(S.top==0) exit(0);
    else
    e=S.base[--S.top]; 
    }
    
    
    
    
    //括号匹配 
    int AllBrackets_Test(char *str) {
    char *p,ch;
    SqStack S;
    InitStack(S);
    for(p=str;*p;p++){
    if(*p=='(' || *p=='[' || *p=='{') 
    Push( S, *p );
    else if(*p==')' || *p==']' || *p=='}'){
    if(StackEmpty(S)) return 0;
    Pop( S,ch );
    if( *p==')' && ch!='(') return 0;
    if( *p==']' && ch!='[') return 0;
    if( *p=='}' && ch!='{') return 0; //不匹配返回0  
    }
    }
    if(StackEmpty(S))         //栈为空则匹配 
    {printf("匹配！\n") ;
    return 0;
    }
    else
    printf("不匹配！\n"); 
    }
    
    
    int main(){
    char a[100];
    printf("输入一串括号：\n");
    gets(a);
    AllBrackets_Test(a);
    return 0;
    }