C语言实现括号匹配的方法

括号匹配的问题

括号匹配是指在一个字符串中，不同类型的括号必须按照正确的顺序出现。例如，"(())"是一个合法的括号序列，而"())("则不是。

在C语言中，我们可以使用堆栈（stack）来实现括号匹配。堆栈是一种先入后出（LIFO）的数据结构，我们可以使用它来检查括号序列的有效性。

算法思路

1. 定义一个堆栈，用于存储遇到的左括号。

2. 遍历输入的字符串，对于每个字符进行如下操作：

    // 如果是左括号，将其压入堆栈
    if (character == '(' || character == '[' || character == '{') {
        push(stack, character);
    }
    // 如果是右括号，检查堆栈的栈顶元素是否与当前字符匹配
    else if (character == ')' || character == ']' || character == '}') {
        if (isEmpty(stack) || !isMatchingPair(top(stack), character)) {
            return false; // 括号不匹配
        } else {
            pop(stack); // 匹配成功，弹出栈顶元素
        }
    }

3. 遍历完字符串后，如果堆栈为空，则说明所有括号都匹配成功；否则，括号不匹配。

函数实现

#include 
#include 
#include 

// 定义堆栈节点
typedef struct Node {
    char data;
    struct Node* next;
} Node;

// 创建一个堆栈
Node* createStack() {
    return NULL;
}

// 判断堆栈是否为空
bool isEmpty(Node* stack) {
    return stack == NULL;
}

// 将元素压入堆栈
void push(Node** stack, char data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *stack;
    *stack = newNode;
}

// 弹出堆栈顶部的元素
void pop(Node** stack) {
    if (isEmpty(*stack)) {
        printf("Error: Stack is empty");
        return;
    }
    Node* temp = *stack;
    *stack = (*stack)->next;
    free(temp);
}

// 获取堆栈顶部的元素
char top(Node* stack) {
    if (isEmpty(stack)) {
        return '\0';
    }
    return stack->data;
}

// 判断括号是否匹配
bool isMatchingPair(char left, char right) {
    if (left == '(' && right == ')') {
        return true;
    }
    if (left == '[' && right == ']') {
        return true;
    }
    if (left == '{' && right == '}') {
        return true;
    }
    return false;
}

// 检查括号匹配是否正确
bool checkBracketMatching(const char* str) {
    Node* stack = createStack();
    int i = 0;
    while (str[i] != '\0') {
        char character = str[i];
        if (character == '(' || character == '[' || character == '{') {
            push(&stack, character);
        } else if (character == ')' || character == ']' || character == '}') {
            if (isEmpty(stack) || !isMatchingPair(top(stack), character)) {
                return false;
            } else {
                pop(&stack);
            }
        }
        i++;
    }
    return isEmpty(stack);
}

// 测试样例
int main() {
    const char* str1 = "()";
    const char* str2 = "([{}])";
    const char* str3 = "({[}])";
    printf("括号匹配结果: %s\n", checkBracketMatching(str1) ? "正确" : "错误");
    printf("括号匹配结果: %s\n", checkBracketMatching(str2) ? "正确" : "错误");
    printf("括号匹配结果: %s\n", checkBracketMatching(str3) ? "正确" : "错误");
    return 0;
}

总结

通过使用堆栈和遍历输入字符串的方式，我们可以轻松地实现括号匹配的功能。这个算法的时间复杂度为O(n)，其中n是字符串的长度。它具有很好的效率，并且在许多编程问题中都有应用。

代码中使用了一个堆栈数据结构来存储遇到的左括号，并在遇到右括号时检查栈顶元素是否与其匹配。如果括号顺序正确，最终堆栈将为空。

在实际应用中，我们可以使用这个算法来检查代码中的括号匹配情况，或者在日常生活中检查数学表达式的括号是否正确嵌套。

希望这个解答对你有帮助，如果你有任何问题，请随时提问。