编号0017
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-parentheses
我们假设字符串有这些符号组成
当我们遍历到左括号的时候 我们就对其进行压栈操作
c语言代码表示如下
typedef char StackType; typedef struct Stack { StackType* a; //储存数据的大小 int Top; //栈顶 int Capacity; //数组容量大小 }ST; void StackInit(ST* p) { assert(p); p->a = NULL; p->Top = 0; p->Capacity = 0; } StackType StackTop (ST* p) { assert(p); return p->a[p->Top - 1]; } void StackPush(ST* p, StackType x) { assert(p); if (p->Top==p->Capacity) { int NewCapacity = p->Capacity == 0 ? 4: p->Capacity * 2; StackType* Tmp = realloc(p->a,NewCapacity*sizeof(StackType)); if (Tmp==NULL) { perror("StackPush realloc"); } else { p->Capacity = NewCapacity; p->a = Tmp; } } p->a[p->Top] = x; p->Top++; } void StackPop(ST* p) { assert(p); assert(p->Top > 0); p->Top--; } void StackPrint(ST* p) { assert(p); while (p->Top>0) { printf("%d ", p->a[p->Top - 1]); StackPop(p); } } int StackSize(ST* p) { assert(p); return p->Top; } bool StackEmpty(ST* p) { assert(p); return p->Top==0; } void StackDestroy(ST* p) { assert(p); free(p->a); p->a == NULL; p->Capacity = 0; p->Top = 0; } ST st1; bool isValid(char * s) { StackInit(&st1); while(*s) { if(*s=='('||*s=='{'||*s=='[') { StackPush(&st1,*s); s++; } else { StackType top = StackTop(&st1); StackPop(&st1); if((*s==')'&& top!='(') || (*s==']'&& top!='[') || (*s=='}'&& top!='{') ) { StackDestroy(&st1); return false; } else { s++; } } } StackDestroy(&st1); return true; }
我们提交试试看
咦 我们可以发现 这里好像没有匹配成功过 直接遍历完了也返回true了
那么这里我们可以判断下是否为空 如果为空我们返回假就好了
我们再测试下看看
咦 有出错了
我们发现 这里栈上还没有数据 直接就开始出栈了 当然就报错了
那么我们再打个补丁
咦 有出错了
我们发现 这里栈上还没有数据 直接就开始出栈了 当然就报错了
那么我们再打个补丁
// 如果遇到了后面的括号 且栈为空 直接return false if(StackEmpty(&st1)) { return false; }
之后我们再试试看
成功通过所有测试用例
