(20)王道数据结构-栈在括号匹配中的应用

基本思想

遇到左括号就入栈，遇到右括号，就“消耗”一个左括号。

扫描到右括号且栈空，右括号单身

处理完所有括号后，栈非空，左括号单身

实现代码

#include<stdio.h>
#define MaxSize 10      //定义栈中元素最大个数
typedef struct {
    char data[MaxSize];  //静态数组存放栈中元素
    int  top;           //栈顶指针
} SqStack;
void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool Push(SqStack &S, char x);
bool Pop(SqStack &S, char &x);
char GetTop(SqStack S, char &x);
bool BracketCheck(char str[], int length);
int main(void) {
    char str[] = "[(())]";
    int length = sizeof(str) - 1;
    //括号匹配判断
    if (BracketCheck(str, length)) {
        printf("括号匹配成功!\n");
    }
    
    char err_str[] = "[(()))]";
    length = sizeof(err_str) - 1;
    if (!BracketCheck(err_str, length)) {
        printf("括号匹配失败!\n");
    }
    return 0;
}

//初始化栈
void InitStack(SqStack &S) {
    S.top = -1;     //初始化栈顶指针
}

//判断栈空
bool StackEmpty(SqStack S) {
    if (S.top == -1) {  //栈空
        return true;
    } else {
        return false;
    }
}

//新元素入栈
bool Push(SqStack &S, char x) {
    if (S.top == MaxSize - 1) { //栈满报错
        return false;
    }
    S.top = S.top + 1;          //指针加1
    S.data[S.top] = x;          //新元素入栈
    return true;
}

//出栈操作
bool Pop(SqStack &S, char &x) {
    if (S.top == -1) {  //栈空，报错
        return false;
    }
    x = S.data[S.top];  //栈顶元素先出栈
    S.top = S.top - 1;  //指针减1
    return true;
}

//读取栈顶元素
char GetTop(SqStack S, char &x) {
    if (S.top == -1) {  //栈空，报错
        return false;
    }
    x = S.data[S.top];  //x记录栈顶元素
    return x;
}

bool BracketCheck(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 (StackEmpty(S)) {    //扫到有括号且当前栈空
                return false;
            }
            char topElem;
            Pop(S,topElem);     //栈顶元素先出栈
            if (str[i] == ')' && topElem != '(') {
                return false;
            }
            if (str[i] == ']' && topElem != '[') {
                return false;
            }
            if (str[i] == '{' && topElem != '{') {
                return false;
            }
        }
    }
    return StackEmpty(S);   //检索完全部括号后，栈空说明匹配成功
}

扫描过程

依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。

匹配失败的情况：

①左括号单身

②右括号单身

③左右括号不匹配