题解 | 括号配对问题

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

#define MAX_SIZE 100000

typedef struct
{
    char data[MAX_SIZE];
    int top;
} ArrayStack;

//初始化
void initArrayStack(ArrayStack* stack)
{
    stack->top = -1;
}

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

//判断栈是否为满
bool isFull(ArrayStack* stack)
{
    return stack->top == MAX_SIZE - 1;
}

//入栈
void push(ArrayStack* stack, char num)
{
    if(isFull(stack))
    {
        printf("Full\n");
        return;
    }
    //stack->top++;
    //stack->data[stack->top] = num;
    stack->data[++stack->top] = num;
}

//出栈
void pop(ArrayStack* stack)
{
    if(isEmpty(stack))
    {
        printf("Empty\n");
        return;
    }
    stack->top--;
    stack->data[stack->top];
}

//获取栈顶元素
char query(ArrayStack* stack)
{
    if(isEmpty(stack))
    {
        printf("Empty\n");
        return false;
    }
    return stack->data[stack->top];
}

//获取栈的长度
int size(ArrayStack* stack)
{
    return stack->top++;
}

//括号匹配
bool isBracketsBalanced(char* s)
{
    //声明并初始化顺序栈
    ArrayStack stack;
    initArrayStack(&stack);

    for(int i = 0; s[i] != '\0'; i++)
    {
        if(s[i] == '(' || s[i] == '[')//如果遇到左括号'(' '[',压入栈内
        {
            push(&stack, s[i]);
        }
        else if(s[i] == ')' || s[i] == ']')//如果遇到右括号')' ']',检查栈顶元素是否与当前右括号匹配
        {
            if(isEmpty(&stack))//栈为空或栈顶元素不匹配，返回false
            {
                return false;
            }

            char top_element = query(&stack);
            if((s[i] == ')' && top_element != '(')||(s[i] == ']' && top_element != '['))
            {
                return false;
            }
            //如果匹配，弹出栈顶元素继续处理
            pop(&stack);
        }
    }
    //最后检查整个栈是否为空，为空表示所有括号都匹配
    return isEmpty(&stack);
}


int main()
{
    char s[MAX_SIZE] ={'\0'};
    scanf("%s",s);
    getchar();

    if(isBracketsBalanced(s))
    {
        printf("true\n");
    }
    else
    {
        printf("false\n");
    }

    return 0;
}