题解 | 括号配对问题

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define N 10000


char* IsBracket(char *S)
{
    char *arr = (char *)malloc(sizeof(char) * N);
    if(arr == NULL)
    {
        return NULL;
    }

    int j = 0;
    for(int i = 0;S[i] != '\0';i++)
    {
        if(S[i] == '(' || S[i] == ')' || S[i] == '[' || S[i] == ']' || S[i] == '{' || S[i] == '}')
        {
            arr[j]  = S[i];
            j++;
        }
    }

    arr[j] = '\0';//注意得添加字符串结束符
    return arr;
}

char pairs(char a)
{
    if(a == ')')
    {
        return '(';
    }

    if(a == ']')
    {
        return '[';
    }

    if(a == '}')
    {
        return '{';
    }

    return 0;
}

bool IsLegal(char *s)
{
    if(s == NULL)
    {
        return true;
    }
    int len = strlen(s);

    if(len % 2 == 1)
    {
        return false;
    }

    //使用char数组作为栈
    char stk[len + 1];
    int top = 0;

    for(int i = 0;i < len;i++)
    {
        char ch = pairs(s[i]);
        if(ch)
        {
            if(top == 0 || stk[top - 1] != ch)
            {
                return false;
            }
            top--;
        }
        else
        {
            stk[top++] = s[i];
        }
    }
    return top == 0;
}


int main() {
    char S[N];

    if(scanf("%s",S) != 1)
    {
        printf("true");
        return 0;
    }

    char *newS = IsBracket(S);//指针接收，不用数组接收 char newS[N] = IsBracket(S);

    if(newS == NULL)
    {
        printf("true");
        return 0;
    }

    bool flag = IsLegal(newS);
    printf("%s",flag == 1 ? "true" : "false");

    free(newS);
    return 0;
}