括号匹配问题 栈c语言

### 回答1：
下面是一个简单的括号匹配问题的栈实现，使用C语言：

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

#define MAX_STACK_SIZE 100

typedef struct {
    char data[MAX_STACK_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAX_STACK_SIZE - 1;
}

void push(Stack *s, char c) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        exit(1);
    }
    s->top++;
    s->data[s->top] = c;
}

char pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        exit(1);
    }
    char c = s->data[s->top];
    s->top--;
    return c;
}

int isMatched(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

int isBalanced(char *s) {
    Stack stack;
    initStack(&stack);
    char c;
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            push(&stack, s[i]);
        } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
            if (isEmpty(&stack)) {
                return 0;
            }
            c = pop(&stack);
            if (!isMatched(c, s[i])) {
                return 0;
            }
        }
    }
    return isEmpty(&stack);
}

int main() {
    char s1[] = "((()))";
    char s2[] = "((())";
    char s3[] = "(()))";
    char s4[] = "{{()}[()]}";
    char s5[] = "{{()}[()]))";
    printf("%s: %d\n", s1, isBalanced(s1));
    printf("%s: %d\n", s2, isBalanced(s2));
    printf("%s: %d\n", s3, isBalanced(s3));
    printf("%s: %d\n", s4, isBalanced(s4));
    printf("%s: %d\n", s5, isBalanced(s5));
    return 0;
}

以上代码使用了一个`Stack`结构体来表示栈，其中`data`数组存储栈中的元素，`top`表示栈顶的位置。`initStack`函数用于初始化栈，`isEmpty`和`isFull`函数用于判断栈是否为空或已满，`push`和`pop`函数用于向栈中压入或弹出元素。`isMatched`函数用于判断左右括号是否匹配，`isBalanced`函数用于判断一个字符串中的括号是否匹配。在`isBalanced`函数中，遍历字符串中的每个字符，如果是左括号则入栈，如果是右括号则弹出栈顶元素并判断左右括号是否匹配。最后判断栈是否为空，如果为空则表示括号匹配，否则表示括号不匹配。在`main`函数中，测试了几个字符串的括号匹配情况。

### 回答2：
括号匹配问题是指在一个字符串中，判断括号的使用是否正确配对。例如，"((()))"、"()()()"都是括号正确匹配的使用，而"(()"、")()("则是括号不正确匹配的使用。

解决这个问题可以使用栈来进行判断。具体步骤如下：
1. 创建一个栈用于存储左括号，比如使用数组来模拟栈。同时定义一个变量flag用于标记括号的匹配情况，初始值为1。
2. 逐个遍历字符串中的字符。
3. 如果遇到左括号，则将其入栈。
4. 如果遇到右括号，则判断栈顶元素是否为左括号。
a. 如果是左括号，则将栈顶元素出栈。
b. 如果不是左括号，则说明括号不匹配，将flag的值设为0。
5. 循环结束后，如果栈为空且flag为1，则说明字符串中的括号正确匹配，否则括号不匹配。

下面是用C语言实现上述算法的示例代码：

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

#define MAX_SIZE 100

int isBracketMatching(char str[]) {
    int stack[MAX_SIZE], top = -1;
    int flag = 1;
    int len = strlen(str);
    
    for (int i = 0; i < len; i++) {
        if (str[i] == '(') {
            stack[++top] = '(';
        }
        else if (str[i] == ')') {
            if (top == -1 || stack[top--] != '(') {
                flag = 0;
                break;
            }
        }
    }
    
    if (top != -1 || flag == 0) {
        flag = 0;
    }
    
    return flag;
}

int main() {
    char str[MAX_SIZE];
    printf("请输入括号字符串：");
    scanf("%s", str);
    
    if (isBracketMatching(str)) {
        printf("括号正确匹配。\n");
    }
    else {
        printf("括号不匹配。\n");
    }
    
    return 0;
}

以上就是使用C语言实现括号匹配问题的方法。主要是通过遍历字符串并使用栈来进行匹配，最后判断栈是否为空且flag是否为1，来判断括号是否正确匹配。

### 回答3：
括号匹配问题是通过使用栈来解决的一类经典问题。其思想是遍历字符串中的字符，当遇到左括号时，将其入栈；当遇到右括号时，将栈顶元素出栈，并判断出栈的左括号与右括号是否匹配。如果所有的括号都能正确匹配，最终栈会为空。

在C语言中实现括号匹配问题可以使用数组模拟栈的数据结构。首先定义一个用来存储左括号的数组和一个用来存储右括号的数组，这两个数组的下标从0开始。然后遍历给定的字符串，当遇到左括号时，将其添加到左括号数组中；当遇到右括号时，判断右括号数组中最后一个括号是否与当前右括号匹配，如果匹配，则将右括号数组中最后一个括号出栈，否则说明括号不匹配。最后判断左括号数组是否为空，如果为空则说明所有括号都匹配成功，反之则说明有括号未匹配成功。

以下是一个用C语言实现的括号匹配问题的代码示例：

#include <stdio.h>

#define MAX_SIZE 100

char left_bracket_stack[MAX_SIZE];
int left_top = -1;

char right_bracket_stack[MAX_SIZE];
int right_top = -1;

void push(char bracket, char stack[], int* top) {
    if (*top < MAX_SIZE - 1) {
        stack[++(*top)] = bracket;
    }
}

char pop(char stack[], int* top) {
    if (*top >= 0) {
        return stack[(*top)--];
    }
    return '\0';
}

int is_match(char left, char right) {
    if ((left == '(' && right == ')') ||
        (left == '[' && right == ']') ||
        (left == '{' && right == '}')) {
        return 1;
    }
    return 0;
}

int is_bracket_match(char* expr) {
    while (*expr) {
        if (*expr == '(' || *expr == '[' || *expr == '{') {
            push(*expr, left_bracket_stack, &left_top);
        }
        else if (*expr == ')' || *expr == ']' || *expr == '}') {
            if (left_top == -1 || !is_match(pop(left_bracket_stack, &left_top), *expr)) {
                return 0;
            }
        }
        expr++;
    }
    return left_top == -1;
}

int main() {
    char expr[MAX_SIZE];
    printf("请输入一个表达式：");
    scanf("%s", expr);
    if (is_bracket_match(expr)) {
        printf("括号匹配成功！\n");
    }
    else {
        printf("括号匹配失败！\n");
    }
    return 0;
}

以上就是用C语言实现括号匹配问题的一个示例，通过使用栈来检查括号的匹配关系，最终确定是否匹配成功。