C语言顺序栈实现括号匹配算法

本代码使用C语言实现了一个顺序栈，并利用该栈结构来判断括号字符串是否匹配。代码包含详细的注释，并附带测试用例，方便读者理解和学习。

代码实现

#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
#define gets(str) gets_s(str)     //解决vs不能用gets
#define scanf scanf_s

typedef char ElemType;
typedef int Status;

typedef struct stack {
    ElemType* data;
    int top;
} SqStack;

Status match(SqStack& s, char* str) {
    int i = 0, flag = 0;
    ElemType e;
    while (str[i] != '\0') {
        switch (str[i]) {
        case '(': 
        case '[': 
        case '{':
            push(s, str[i]);
            break;
        case ')':
            if (pop(s, e) != OK || e != '(') {
                flag = 1;
            }
            break;
        case ']':
            if (pop(s, e) != OK || e != '[') {
                flag = 1;
            }
            break;
        case '}':
            if (pop(s, e) != OK || e != '{') {
                flag = 1;
            }
            break;
        default:
            break;
        }
        if (flag) {
            return ERROR;
        }
        i++;
    }

    if (!flag && stackEmpty(s)) {
        printf("括号匹配成功!\n");
    }
    else {
        printf("括号匹配失败!\n");
    }
    return OK;
}

void initStack(SqStack& st) {
    st.data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    st.top = -1;
}

Status stackEmpty(SqStack st) {
    if (st.top == -1) {
        return TRUE;
    }
    else {
        return FALSE;
    }
}

Status push(SqStack& st, ElemType x) {
    if (st.top == MAXSIZE - 1) {
        return ERROR;
    }
    st.data[++st.top] = x;
    return OK;
}

Status pop(SqStack& st, ElemType& x) {
    if (st.top == -1) {
        return ERROR;
    }
    x = st.data[st.top--];
    return OK;
}

void printStack(SqStack& st) {
    printf("顺序栈显示：");
    for (int i = 0; i <= st.top; i++) {
        printf("%c ", st.data[i]);
    }
    printf("\n");
}

int main() {
    SqStack st;
    initStack(st);

    char str[20];
    printf("请输入括号字符串：");
    gets(str);

    if (match(st, str) == OK) {
        printf("括号匹配成功。\n");
    }
    else {
        printf("括号匹配失败。\n");
    }

    return 0;
}

代码说明

数据结构定义
- 使用SqStack结构体来表示顺序栈，包含data指针指向栈元素数组，top表示栈顶指针。
函数说明
- initStack函数用于初始化栈，分配内存并设置栈顶指针为-1。
- stackEmpty函数用于判断栈是否为空，若栈顶指针为-1则为空。
- push函数用于将元素入栈，若栈满则返回错误。
- pop函数用于将栈顶元素出栈，若栈空则返回错误。
- match函数是核心函数，用于判断括号字符串是否匹配。
  - 遍历字符串，遇到左括号则入栈。
  - 遇到右括号则出栈，并与对应的左括号比较。
  - 如果匹配失败或栈为空，则返回错误。
- printStack函数用于打印栈中元素。
测试用例
- 输入字符串 ( [ { } ] )，输出 括号匹配成功！
- 输入字符串 ( [ { } ]，输出 括号匹配失败！

总结

本代码使用顺序栈实现了简单的括号匹配功能，可以作为学习数据结构和算法的入门示例。

注意: 本代码仅实现了简单的括号匹配功能，对于复杂的表达式可能无法判断。

希望本代码能帮助您理解顺序栈以及其应用场景。