栈的应用-括号匹配

括号匹配

数组模拟栈

bool bracketCheck(char str[], int length) {
    ElemType data[MaxSize];
    int top = -1;
    for (int i = 0; i < length; i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            data[++top] = str[i];
        }
        else {
            if (top == -1) {
                return false;
            }
            ElemType e = data[top--];
            if (!(e == '(' && str[i] == ')' || e == '[' && str[i] == ']' || e == '{' && str[i] == '}')) {
                return false;
            }
        }
    }
    return top == -1;
}

栈操作

#include<stdio.h>
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct SqStack {
    ElemType data[MaxSize];
    int top;
}SqStack;

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

//判空
bool StackEmpty(SqStack S) {
    return S.top == -1;
}

//入栈
bool Push(SqStack& S, ElemType e) {
    if (S.top == MaxSize-1) {
        return false;
    }
    S.data[++S.top] = e;
    return true;
}

///出栈
bool Pop(SqStack& S,ElemType &e) {
    if (S.top == -1) {
        return false;
    }
    e = S.data[S.top--];
    return true;
}

//获取栈顶元素
bool GetTop(SqStack S, ElemType& e) {
    if (S.top == -1) {
        return false;
    }
    e = S.data[S.top];
    return true;
}

//括号匹配
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 e;
            Pop(S, e);
            if (!(e == '(' && str[i] == ')' || e == '[' && str[i] == ']' || e == '{' && str[i] == '}'))
            {
                return false;
            }
        }
    }
    return StackEmpty(S);
}
int main()
{
    char str[] = "(([]))[]{}{{}}";
    printf("括号0错误/1正确:%d\n",bracketCheck(str, strlen(str)));
    return 0;
}