一、题目：
函数原型：bool isValid(char* s)
二、思路：
利用栈来解这道题会方便许多：
遍历字符串s，当遇到左括号就将其压入栈中；遇到右括号首先判断栈是否为空，如果为空说明左右括号数量不匹配返回false，再判断它与左括号是否匹配，如果不匹配返回false，如果匹配则将栈顶元素出栈。全部遍历完成后，如果栈不为空，说明左右括号数量不匹配，返回false，如果栈为空则返回true。
三、代码：
//顺序栈的结构定义 typedef char STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; //顺序栈的初始化 void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0;//top指针指向栈顶元素的下一位 pst->capacity = 0;//顺序栈的容量 } //顺序栈的打印 void STPrint(ST pst) { for (int i = 0; i < pst.top; i++) { printf("%d ", pst.a[i]); } printf("\n"); } //顺序栈的入栈 void STPush(ST* pst, STDataType x) { assert(pst); //检查扩容 if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity; STDataType* p = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType)); if (p == NULL) { perror("realloc fail"); exit(-1); } else { pst->a = p; pst->capacity = newcapacity; } } pst->a[pst->top++] = x; } //顺序栈出栈 void STPop(ST* pst) { assert(pst); assert(pst->top > 0); pst->top--; } //求顺序栈栈顶元素 STDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top - 1]; } //顺序栈判空 bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } //顺序栈销毁 void STDestroy(ST* pst) { assert(pst); if (pst->a != NULL) { free(pst->a); pst->a = NULL; pst->top = 0; pst->capacity = 0; } } bool isValid(char* s) { //定义顺序栈 ST st; //初始化顺序栈 STInit(&st); int len=strlen(s); for(int i=0;i<len;i++) { if(s[i]=='('||s[i]=='{'||s[i]=='[') { STPush(&st,s[i]); } else if(s[i]==')'||s[i]=='}'||s[i]==']') { if(STEmpty(&st)) return false; else { if((STTop(&st)=='('&&s[i]!=')')||(STTop(&st)=='{'&&s[i]!='}')||(STTop(&st)=='['&&s[i]!=']')) return false; STPop(&st); } } } if(!STEmpty(&st)) return false; else return true; }
