栈的应用------括号匹配

佚名 4年前 (2020-03-11) 算法 568人围观抢沙发百度已收录

//使用栈进行括号匹配
#include <stdio.h>
#include <malloc.h>

#define MaxSize 10

typedef struct{
    char data[MaxSize];
    int top;
}SqStack;

void InitStack(SqStack *);  //初始化
int StackEmpty(SqStack);    //判断栈是否为空
void Push(SqStack * , char);        //入栈
char Pop(SqStack * , char *);           //出栈 
int BracketCheck(char [] , int);        //括号检查 

int main(void){
    char str[] = "((([{}}])))";
    int length = strlen(str);
    if(BracketCheck(str , length)){
        printf("括号成对！");
    }else{
        printf("括号不成对！");
    } 
    return 0;
} 

//初始化
void InitStack(SqStack *S){
    S->top = -1;
}

//判断栈是否为空
int StackEmpty(SqStack S){
    if(S.top == -1){
        return 1;
    }
    return 0;
}

//入栈
void Push(SqStack *S , char c){
    if(S->top == MaxSize - 1){
        printf("栈满！\n");
        return;
    }else{
        S->data[++S->top] = c;
    }
}

//出栈
char Pop(SqStack *S , char *e){
    if(StackEmpty(*S)){
        printf("栈为空！\n");
    }else{
        (*e) = S->data[(S->top)--];
    }
    return (*e);
}

//括号检查 
int BracketCheck(char str[] , int len){
    SqStack S;
    InitStack(&S);
    int i;
    for(i = 0 ; i < len ; i ++){
        if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
            Push(&S , str[i]);
        }else{
            if(StackEmpty(S)){
                return 0;
            }else{
                char topElem;
                Pop(&S , &topElem);
                if(str[i] == ')' && topElem != '('){
                    return 0;
                }
                if(str[i] == ']' && topElem != '['){
                    return 0;
                }
                if(str[i] == '}' && topElem != '{'){
                    return 0;
                }
            }
        }
    }
    return StackEmpty(S);
}