数据结构07-括号匹配

数据结构07-括号匹配

代码

#include <stdbool.h>
#include <stdio.h>
#include <malloc.h>

#define STACK_MAX_SIZE 10 // 定义栈的最大大小

/**
 * 表示整数的线性栈。关键是数据。
 */
typedef struct CharStack {
    int top; // 栈顶指针

    char data[STACK_MAX_SIZE]; // 数据数组，最大长度固定
} *CharStackPtr;

/**
 * 输出栈的内容。
 */
void outputStack(CharStackPtr paraStack) {
    for (int i = 0; i <= paraStack->top; i ++) {
        printf("%c ", paraStack->data[i]);
    }// 循环结束
    printf("\r\n");
}// 结束 outputStack

/**
 * 初始化一个空的字符栈。这个函数没有错误检查。
 * @param paraStackPtr 栈的指针。必须是指针才能改变栈。
 * @param paraValues 存储所有元素的int数组。
 */
CharStackPtr charStackInit() {
    CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(struct CharStack));
    resultPtr->top = -1; // 初始化栈顶为-1，表示空栈

    return resultPtr;
}// 结束 charStackInit

/**
 * 将一个元素推入栈。
 * @param paraValue 要推入的值。
 */
void push(CharStackPtr paraStackPtr, int paraValue) {
    // 步骤 1. 检查空间。
    if (paraStackPtr->top >= STACK_MAX_SIZE - 1) {
        printf("Cannot push element: stack full.\r\n");
        return;
    }// 结束 if

    // 步骤 2. 更新栈顶。
    paraStackPtr->top ++;

    // 步骤 3. 推入元素。
    paraStackPtr->data[paraStackPtr->top] = paraValue;
}// 结束 push

/**
 * 从栈中弹出一个元素。
 * @return 被弹出的值。
 */
char pop(CharStackPtr paraStackPtr) {
    // 步骤 1. 检查空间。
    if (paraStackPtr->top < 0) {
        printf("Cannot pop element: stack empty.\r\n");
        return '\0';
    }// 结束 if

    // 步骤 2. 更新栈顶。
    paraStackPtr->top --;

    // 步骤 3. 弹出元素。
    return paraStackPtr->data[paraStackPtr->top + 1];
}// 结束 pop

/**
 * 测试 push 函数。
 */
void pushPopTest() {
    printf("---- pushPopTest begins. ----\r\n");
    char ch;
    
    // 初始化。
    CharStackPtr tempStack = charStackInit();
    printf("After initialization, the stack is: ");
    outputStack(tempStack);

    // 推入。
    for (ch = 'a'; ch < 'm'; ch ++) {
        printf("Pushing %c.\r\n", ch);
        push(tempStack, ch);
        outputStack(tempStack);
    }// 结束 for

    // 弹出。
    for (int i = 0; i < 3; i ++) {
        ch = pop(tempStack);
        printf("Pop %c.\r\n", ch);
        outputStack(tempStack);
    }// 结束 for

    printf("---- pushPopTest ends. ----\r\n");
}// 结束 pushPopTest

/**
 * 判断括号是否匹配。
 * 
 * @param paraString 给定的表达式字符串。
 * @return 是否匹配。
 */
bool bracketMatching(char* paraString, int paraLength) {
    // 步骤 1. 初始化栈，底部推入一个 '#'。
    CharStackPtr tempStack = charStackInit();
    push(tempStack, '#');
    char tempChar, tempPopedChar;

    // 步骤 2. 处理字符串。
    for (int i = 0; i < paraLength; i++) {
        tempChar = paraString[i];

        switch (tempChar) {
        case '(':
        case '[':
        case '{':
            push(tempStack, tempChar);
            break;
        case ')':
            tempPopedChar = pop(tempStack);
            if (tempPopedChar != '(') {
                return false;
            } // 结束 if
            break;
        case ']':
            tempPopedChar = pop(tempStack);
            if (tempPopedChar != '[') {
                return false;
            } // 结束 if
            break;
        case '}':
            tempPopedChar = pop(tempStack);
            if (tempPopedChar != '{') {
                return false;
            } // 结束 if
            break;
        default:
            // 什么也不做。
            break;
        }// 结束 switch
    } // 结束 for

    tempPopedChar = pop(tempStack);
    if (tempPopedChar != '#') {
        return false;
    } // 结束 if

    return true;
}// 结束 bracketMatching

/**
 * 单元测试。
 */
void bracketMatchingTest() {
    char* tempExpression = "[2 + (1 - 3)] * 4";
    bool tempMatch = bracketMatching(tempExpression, 17);
    printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);

    tempExpression = "( )  )";
    tempMatch = bracketMatching(tempExpression, 6);
    printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);

    tempExpression = "()()(())";
    tempMatch = bracketMatching(tempExpression, 8);
    printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);

    tempExpression = "({}[])";
    tempMatch = bracketMatching(tempExpression, 6);
    printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);

    tempExpression = ")(";
    tempMatch = bracketMatching(tempExpression, 2);
    printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);
}// 结束 bracketMatchingTest

/**
 * 程序入口。
 */
void main() {
    // pushPopTest(); // 测试推入和弹出功能
    bracketMatchingTest(); // 测试括号匹配功能
}// 结束 main

总结： 这段代码实现了一个固定大小的字符栈（最大为10个元素），包括基本操作如初始化、推入（push）和弹出（pop）。它还包括一个用于输出栈内容的辅助函数和两个测试函数：pushPopTest用于测试推入和弹出操作，bracketMatchingTest用于测试括号匹配问题，检查给定字符串中的括号是否正确匹配。主函数main调用了括号匹配测试函数。代码中的每个函数都有详细的中文注释，说明了其功能和工作原理。

运行结果