c 用栈实现括号匹配算法

括号匹配算法可以使用栈来实现。具体步骤如下：

1. 创建一个栈，用于存储左括号。
2. 从左到右遍历字符串中的每个字符。
3. 如果当前字符是左括号，则将其压入栈中。
4. 如果当前字符是右括号，则从栈中弹出一个左括号。如果弹出的左括号与当前右括号不匹配，则说明括号不匹配，返回false。
5. 如果遍历完字符串后栈中还有左括号未被匹配，则说明括号不匹配，返回false。
6. 如果遍历完字符串后栈中没有左括号未被匹配，则说明括号匹配，返回true。

下面是用 C 语言实现的括号匹配算法：

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

#define STACK_SIZE 100

char stack[STACK_SIZE];  // 栈
int top = -1;            // 栈顶指针

// 判断栈是否为空
bool is_empty()
{
    return top == -1;
}

// 判断栈是否已满
bool is_full()
{
    return top == STACK_SIZE - 1;
}

// 入栈
void push(char c)
{
    if (is_full()) {
        printf("Stack is full!\n");
        return;
    }
    stack[++top] = c;
}

// 出栈
char pop()
{
    if (is_empty()) {
        printf("Stack is empty!\n");
        return '\0';
    }
    return stack[top--];
}

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

// 判断字符串中的括号是否匹配
bool is_balanced(char* str)
{
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            push(str[i]);  // 左括号入栈
        } else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
            char left = pop();  // 弹出栈顶的左括号
            if (!is_matching(left, str[i])) {
                return false;  // 括号不匹配
            }
        }
    }
    return is_empty();  // 如果栈为空，则说明括号匹配
}

int main()
{
    char str[100];
    printf("Enter a string: ");
    scanf("%s", str);

    if (is_balanced(str)) {
        printf("The parentheses are balanced.\n");
    } else {
        printf("The parentheses are not balanced.\n");
    }

    return 0;
}