括号匹配问题详解

article/2025/10/25 19:11:34

直接看题！！

typedef char STDataType;typedef struct Stack
{STDataType* a;int top;   //栈顶的位置int capacity; //容量
}ST;void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;}void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}void StackPush(ST* ps, STDataType x)
{assert(ps);//容量不足，需要进行扩容if (ps->top == ps->capacity){//增大容量int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//对a指向的数组空间进行增容ps->a = (STDataType*)realloc(ps->a, NewCapacity * sizeof(STDataType));//检查if (ps->a == NULL){printf("realloc fail\n");exit(-1);}ps->capacity = NewCapacity;}//增容之后再入栈//top是从0位置开始所以是先使用再++ps->a[ps->top] = x;ps->top++;
}void StackPop(ST* ps)
{assert(ps);assert(ps->top > 0);--ps->top;}bool StackEmpty(ST* ps)
{assert(ps);if (ps->top > 0){return false;}else{return true;}//return ps->top == 0;
}int StackSize(ST* ps)
{assert(ps);return ps->top;
}STDataType StackTop(ST* ps)
{assert(ps);assert(ps->top > 0);//top是从0开始的return ps->a[ps->top - 1];}

这道题不能用直接数括号数量来进行解答，因为还涉及顺序的问题。括号的匹配用什么来做是最合适的呢？答案是用栈。

根据栈独有的特点，具体操作：1、属于左括号，进行入栈处理。2、属于右括号进行出栈处理，然后进行匹配，不匹配就报错。我们既然选择用C语言来实现，就需要我们自己提前实现一个栈结构。代码如下：

在栈的基础上再进行括号匹配的实现，代码如下：


bool isValid(char * s)
{ST st;//初始化栈StackInit(&st);while(*s){//如果是左括号就入栈if(*s == '(' || *s == '[' || *s == '{'){//入栈StackPush(&st, *s);++s;}else{//若到了这里*s一定是右括号//若只有右括号，栈为空if(StackEmpty(&st)){return false;}//取出栈顶元素char top = StackTop(&st);//出栈StackPop(&st);//这里不要判断相等，判断相等是不能立即得出结果的，括号有三个种类，//就算第一种匹配了，还要判断第二种或者第三种是否匹配//所以这里应判断不等，一旦这种括号不相等就立即能得到结果if((*s == ')' && top != '(')|| (*s == ']' && top != '[')|| (*s == '}' && top != '{')){StackDestroy(&st);//但凡有不匹配都会return falsereturn false;}else{//到这里说明匹配上了，继续比++s;}}}//栈为空，说明所有左括号都匹配了,反之，不为空，返回falsebool tmp = StackEmpty(&st);StackDestroy(&st);//到这里就说明全部都匹配上了return tmp;
}

到目前为止我们所实现出来的代码，逻辑上貌似没有什么问题，但是当我们进行测试的时候，出现了有测试用例没有通过。说明我们的程序还是存在问题的。这就需要我们根据测试用例来对程序进行分析了，一般的方法是根据显示出的不通过的测试用例带入到程序中，然后自己根据程序的逻辑走一遍，相当于执行一遍程序，这样很大可能会发现程序的问题所在。

根据上图的信息我们得知输入的是“[”，也就是*s为‘[’，进入while语句，紧接着进入if语句，然后进行入栈，++s，此时的*s为 '\0'，跳出while循环，最后执行return true；所以才会输出true。但是只有一个括号是不可能匹配的，应该输出false才对。知道了病因，我们就可以对症下药了。具体怎么解决呢？既然他只有一个左括号，但是会跳出while语句，因此我们可以再while语句下面做文章。如果括号都匹配上了，那栈里面应该是没有元素的，所以我们可以在while语句执行完成之后再对进行判空，栈为空就说明都匹配上了，如果栈里面还有落单得到括号。那就肯定没有匹配上。

当我们修改之后，再进行测试，发现还是有执行错误，根据测试用例可以看到，他这次给的是“]”,我们还是按照上面说的方法进行操作。会发现它给的错误信息显示StackTop这个函数的ps->top > 0 是有问题的，再看看一下此函的具体实现，显而易见，是assert语句给出的错误提示，若没有assert的话这里就是越界错误，你不知道在哪里发生的越界，更不容易让人发现。这里也体现出使用assert好处可见一斑。