有效括号
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
- 示例：
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
- 解题思路：
- 这里我们使用栈来解决（先入后出的性质 ）
- 在k题时首先得写个栈出来
- 读取字符时如果遇到左括号则进行入栈操作
- 如果遇到右括号则进行出栈操作，并对出栈数据与读取数据进行匹配
- 当匹配成功时，则继续读取字符
- 当读取结束并且栈中没有数据则为有效字符串，否则相反
图示：
参考代码：
bool isValid(char * s){ //开辟栈 ST st; StackInit(&st); char* str=s; while(*str!='\0') { //遇到左括号入栈 if(*str=='(' ||*str=='{' ||*str=='[') { StackPush(&st,*str); str++; } else { //遇到右括号出栈匹配 if(*str=='}' ||*str==']' ||*str==')') { //为空栈时 if(StackEmpty(&st)) { StackDestroy(&st);//注意栈空间销毁（养成好的习惯） return false; } else { char tmp=StackTop(&st);//获取栈顶数据 StackPop(&st);//出栈 if((*str==']'&&tmp!='[') ||(*str=='}'&&tmp!='{') ||(*str==')'&&tmp!='(')) { //匹配失败 StackDestroy(&st); return false; } else str++; } } } } //遍历完时栈还有数据为被出栈 if(StackEmpty(&st)) { StackDestroy(&st);//结束前先销毁栈 return true; } else { StackDestroy(&st); return false; } }
附上栈源码：
//默认栈数据类型 typedef char STDataType; //栈类型结构 typedef struct Stack { //数组栈（指向数组的指针） STDataType* a; //栈顶位置 int top; //栈容量 int capacity; }ST; //栈初始化 void StackInit(ST* ps); //栈销毁 void StackDestroy(ST* ps); //入栈 void StackPush(ST* ps, STDataType x); //出栈 void StackPop(ST* ps); //获取栈顶数据 STDataType StackTop(ST* ps); //栈使用空间大小 int StackSize(ST* ps); //是否为空栈 bool StackEmpty(ST* ps); //栈初始化 void StackInit(ST* ps) { //避免传入空指针 assert(ps); ps->a = NULL; ps->top = 0;//定义top为栈最后数据的后一个位置 //也可以选择让top为当前最后数据的位置 此时初始化top=-1; ps->capacity = 0; return; } //栈销毁 void StackDestroy(ST* ps) { //避免传入空指针 assert(ps); free(ps->a);//释放开辟的数组栈空间 ps->a = NULL;//置空，避免造成野指针 } //入栈 void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity)//栈满的情况 { //如果原来容量为0则让新容量为4，否则为两倍 int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //调整数组栈大小（特别的：当数组指针为NULL时，realloc的作用和malloc的作用一样） STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(ST) * newcapacity); if (tmp == NULL)//tmp为NULL时则表示调整数组空间失败，那么就打印错误并结束进程 { perror("realloc fail:"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x;//存入数据 ps->top++;//top位置更新 return; } //出栈 void StackPop(ST* ps) { //避免传入空指针 assert(ps); //出栈到数据个数为0结束 if (StackEmpty(ps)) return; ps->top--;//让top减减得到出栈的效果 return; } //获取栈顶数据 STDataType StackTop(ST* ps) { //避免传入空指针 assert(ps); //为空栈时无栈顶数据 assert(!StackEmpty(ps)); return ps->a[ps->top-1];//此时top-1才表示栈顶数据的下标 } //栈使用空间大小 int StackSize(ST* ps) { //避免传入空指针 assert(ps); return ps->top; } //是否为空栈 bool StackEmpty(ST* ps) { //避免传入空指针 assert(ps); return ps->top == 0; }
每日k题无烦恼，点赞学习不得了~
