数据结构（7）栈的应用——括号匹配问题

mumumu

发布于 2022-12-26 16:55:33

4670

发布于 2022-12-26 16:55:33

文章被收录于专栏：blog1blog1

栈的应用——括号匹配问题

什么是括号匹配问题

顾名思义就是把括号组起来，左小括号对右小括号，左中括号对右中括号，左大括号对右大括号，最理想的情况下是匹配成功，即例如以下的括号排列：

( { [ ] } )

和栈的关系

了解什么是括号匹配之后，再来聊聊它和栈的关系。我们知道栈的特性是后进先出，那如果我们这样：把已知的左括号压入栈中，每有一个右括号，就和栈顶元素匹配，如果匹配成功就pop出栈顶元素，这样就把括号匹配问题变为了熟悉的入栈，出栈操作。当然，这只是一个大体思路，具体操作时会有很多临界条件，这里整理出一张流程图：

具体代码实现不算难，但是昨天一直运行出问题，我把每个临界条件都打印输出出来也没找到问题，今早一看原来是入栈函数的临界条件写成了if(S,top = MaxSize-1)….，少了一个等号。

这里直接贴代码了：

栈的相关操作

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define MaxSize 10
//建栈
typedef struct {
    char data[MaxSize];
    int top;
}SqStack;
//初始化
int InitStack(SqStack &S){
    S.top = -1;
    return OK;
}
//入栈
int Push(SqStack &S,char c){
    if(S.top == MaxSize-1){
        return ERROR;//栈满
    }
    S.top = S.top + 1;
    S.data[S.top] = c;
    return OK;
}
//出栈
int Pop(SqStack &S,char *c){
    if(S.top == -1){
        return ERROR;
    }
    *c = S.data[S.top];
    S.top = S.top - 1;
    return OK;
}
//输出
int Print(SqStack S){
    if(S.top == -1){
        return ERROR;
    }
    for(S.top;S.top>-1;S.top--){
        printf("%c\t",S.data[S.top]);
    }
    printf("\n");
    return OK;
}
//栈空
bool Empty(SqStack S){
    if(S.top == -1)
        return true;
    else
        return false;
}

匹配函数

bool pipei(char str[],int length){
    SqStack S;
    InitStack(S);
    for(int i=0;i<length;i++){
        if(str[i]=='(' || str[i]=='[' || str[i]=='{')
            Push(S,str[i]);
        else{
            if(Empty(S)){
                printf("栈空，匹配失败\n");
                return false;
            }
            char ElemTop;
            Pop(S,&ElemTop);
            if(str[i]==')' && ElemTop!='('){
                printf("小括号匹配失败\n");
                return false;
            }
            if(str[i]==']' && ElemTop!='['){
                printf("中括号匹配失败\n");
                return false;
            }
            if(str[i]=='}' && ElemTop!='{'){
                printf("大括号匹配失败\n");
                return false;
            }
        }
    }
    if(Empty(S)== true){
        printf("匹配成功！！！\n");
        return true;
    }
    if(Empty(S)== false){
        printf("匹配失败，栈中还有剩余左括号单身\n");
        return false;
    }
}