c语言括号配对

问题描述

在编程中，一个常见的问题是验证括号是否正确配对。具体而言，在给定的字符串中，我们需要判断括号的使用是否符合规范，即每一个左括号都应该有对应的右括号，并且左括号和右括号的顺序要一致。

解决方法

要解决这个问题，我们可以使用栈这种数据结构。栈是一种后进先出（Last In First Out，LIFO）的数据结构，它支持两个基本操作，即入栈和出栈。我们可以遍历输入的字符串，当遇到左括号时，将其入栈；当遇到右括号时，检查栈顶的元素是否为对应的左括号，如果是配对的括号，则将栈顶元素出栈，继续遍历；如果不是配对的括号，或者栈为空，则认为括号不配对。

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define STACK_SIZE 100

// 定义栈结构
typedef struct {
    int top;
    char data[STACK_SIZE];
} Stack;

// 初始化栈
void initialize(Stack *stack) {
    stack->top = -1;
}

// 将元素入栈
void push(Stack *stack, char c) {
    stack->top++;
    stack->data[stack->top] = c;
}

// 将栈顶元素出栈
void pop(Stack *stack) {
    stack->top--;
}

// 判断栈是否为空
bool isEmpty(Stack *stack) {
    return stack->top == -1;
}

// 判断括号是否配对
bool isParenthesesMatch(char *str, int length) {
    Stack stack;
    initialize(&stack);
    for (int i = 0; i < length; i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            push(&stack, str[i]);
        } else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
            if (isEmpty(&stack)) {
                return false;
            } else {
                char top = stack.data[stack.top];
                if ((top == '(' && str[i] == ')') || (top == '[' && str[i] == ']') || (top == '{' && str[i] == '}')) {
                    pop(&stack);
                } else {
                    return false;
                }
            }
        }
    }
    return isEmpty(&stack);
}

int main() {
    char str[100];
    printf("请输入一个字符串：");
    scanf("%s", str);
    int length = strlen(str);
    if (isParenthesesMatch(str, length)) {
        printf("括号配对正确\n");
    } else {
        printf("括号配对不正确\n");
    }
    return 0;
}

代码解释

上述代码使用了一个结构体来定义栈，然后实现了栈的基本操作：初始化栈、入栈、出栈和判断栈是否为空。主函数中，通过调用isParenthesesMatch函数来判断输入的字符串中的括号是否正确配对。该函数使用了一个栈存储遇到的左括号，并根据遇到的右括号进行对比，如果匹配则出栈，否则认为括号不配对。

总结

通过使用栈这种数据结构，我们可以编写一个简单的程序来验证给定的字符串中的括号是否正确配对。该程序首先初始化一个栈，然后遍历输入的字符串，根据括号类型进行入栈和出栈的操作，最后判断栈是否为空来确定括号是否配对。这种方法在时间复杂度和空间复杂度上都是O(n)，效率较高。