思路：用栈的后进先出的特性，来完成题目的要求
因为C++有库，可以直接用，而C语言没有，所以我们直接把写好的栈拷贝上来用。
首先，完成框架的搭建
其次，再实现循环内的部分。1.左括号入栈 2.右括号出栈匹配
这里在右括号匹配的判断，要注意不要写成两个都相等，这样不能说明全都匹配成功，所以就写成两边不相等，满足则直接return false，不满足则继续循环
每次循环结束，s++。所有循环停止后，没有return false，则return true
看起来好像没有什么问题，对吧？
其实，上述只适用于左右括号数量相等的场景，我们还要考虑两种特殊情况 ：
1.左括号多于右括号
2.右括号多于左括号
左括号多于右括号时，循环结束，栈内元素个数不为0，则用STEmpty判断一下 ，如果为空，与之前相同，返回true，如果不为空，则返回false
右括号多于左括号时，在循环内部，直到栈已经空了，还有右括号要匹配，那么此时也直接返回false
完整代码如下：
typedef char STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; //初始化 void STInit(ST* pst); //销毁 void STDestroy(ST* pst); //压栈 void STPush(ST* pst, STDataType x); //出栈 void STPop(ST* pst); //获取栈顶元素 STDataType STTop(ST* pst); //检测栈是否为空 bool STEmpty(ST* pst); //检测栈中有效元素个数 int STSize(ST* pst); void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0;//top指向栈顶元素的下一个位置 pst->capacity = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->top = pst->capacity = 0; } void STPush(ST* pst, STDataType x) { assert(pst); if (pst->top == pst->capacity) { int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newCapacity; } pst->a[pst->top++] = x; } void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } STDataType STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } int STSize(ST* pst) { assert(pst); return pst->top; } bool isValid(char* s) { ST st; STInit(&st); while (*s) { //1.左括号入栈 //2.右括号出栈匹配 if (*s == '(' ||*s == '[' ||*s == '{') { STPush(&st, *s); } else { //解决右括号多于左括号的问题 if (STEmpty(&st)) { STDestroy(&st); return false; } char top = STTop(&st); STPop(&st); if ((top != '(' && *s == ')') ||(top != '[' && *s == ']') ||(top != '{' && *s == '}')) { STDestroy(&st); return false; } } s++; } //解决左括号多于右括号的问题 bool ret = STEmpty(&st); STDestroy(&st); return ret; }
