题目一 有效的括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
我们假设字符串有这些符号组成
当我们遍历到左括号的时候 我们就对其进行压栈操作
c语言代码表示如下
typedef int STDateType; typedef struct Stack { int* a;//存储数据的大小 int Top;//栈顶 int capacity;//容量大小 }ST; void STInit(ST*ps); void STDestroy(ST* ps); void STPush(ST* ps, STDateType x); void STPop(ST* ps); int STSize(ST* ps); bool STEmpty(ST* ps); STDateType STTop(ST* ps); void STInit(ST* ps) { assert(ps); ps->a = (STDateType*)malloc(sizeof(STDateType)*4); if (ps->a == NULL) { perror("malloc fail"); return; } ps->Top = 0;//top是栈顶元素的下一个位置 ps->capacity = 4; } //销毁 void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->capacity = 0; ps->Top = 0; ps->a = NULL; } //压栈 void STPush(ST* ps, STDateType x) { assert(ps); if (ps->Top == ps->capacity) { STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * ps->capacity * 2); if (tmp == NULL) { perror("realloc fail"); return; } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->Top] = x; ps->Top++; } //出栈 void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps)); ps->Top--; } //个数 int STSize(ST* ps) { assert(ps); return ps->Top; } //判断空 bool STEmpty(ST* ps) { assert(ps); return ps->Top==0; } //栈顶的位置 STDateType STTop(ST* ps) { assert(ps); assert(!STEmpty(ps)); return ps->a[ps->Top - 1]; } bool isValid(char* s) { ST st; STInit(&st); while(*s) { if(*s=='('||*s=='['||*s=='{') { STPush(&st,*s); }else { char top = STTop(&st); STPop(&st); if(*s==')'&&top!='(' ||*s==']'&&top!='[' ||*s=='}'&&top!='{') { return false; } } ++s; } STDestroy(&st); return true; }
我们提交试试看
我们可以发现 这里好像没有匹配成功过 直接遍历完了也返回true了
那么这里我们可以判断下是否为空 如果为空我们返回假就好了
我们再测试下看看
又出错了
我们发现 这里栈上还没有数据 直接就开始出栈了 当然就报错了
那么我们再打个补丁
//如果遇到右边括号且栈为空，直接返回false if(STEmpty(&st)) { return false; }
之后我们再试试看
虽然成功通过所有测试用例
但是我们还要考虑一个内存泄露的问题，还是要加上销毁
完整的代码如下：
typedef int STDateType; typedef struct Stack { int* a;//存储数据的大小 int Top;//栈顶 int capacity;//容量大小 }ST; void STInit(ST*ps); void STDestroy(ST* ps); void STPush(ST* ps, STDateType x); void STPop(ST* ps); int STSize(ST* ps); bool STEmpty(ST* ps); STDateType STTop(ST* ps); void STInit(ST* ps) { assert(ps); ps->a = (STDateType*)malloc(sizeof(STDateType)*4); if (ps->a == NULL) { perror("malloc fail"); return; } ps->Top = 0;//top是栈顶元素的下一个位置 ps->capacity = 4; } //销毁 void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->capacity = 0; ps->Top = 0; ps->a = NULL; } //压栈 void STPush(ST* ps, STDateType x) { assert(ps); if (ps->Top == ps->capacity) { STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * ps->capacity * 2); if (tmp == NULL) { perror("realloc fail"); return; } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->Top] = x; ps->Top++; } //出栈 void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps)); ps->Top--; } //个数 int STSize(ST* ps) { assert(ps); return ps->Top; } //判断空 bool STEmpty(ST* ps) { assert(ps); return ps->Top==0; } //栈顶的位置 STDateType STTop(ST* ps) { assert(ps); assert(!STEmpty(ps)); return ps->a[ps->Top - 1]; } bool isValid(char* s) { ST st; STInit(&st); while(*s) { if(*s=='('||*s=='['||*s=='{') { STPush(&st,*s); }else { if(STEmpty(&st)) { STDestroy(&st); return false; } char top = STTop(&st); STPop(&st); if(*s==')'&&top!='(' ||*s==']'&&top!='[' ||*s=='}'&&top!='{') { STDestroy(&st); return false; } } ++s; } bool ret = STEmpty(&st); STDestroy(&st); return ret; }
也是完美通过
以上便是本文所有内容，如有错误请各位大佬不吝赐教，感谢留言
