leetcode20.括号匹配问题
前言：
💥🎈个人主页:Dream_Chaser～ 🎈💥
✨✨刷题专栏:http://t.csdn.cn/UlvTc
⛳⛳本篇内容:力扣上栈与队列的面试OJ题目
1.问题描述
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
2.前提准备
栈的实现
#pragma once #include<stdlib.h> #include<assert.h> #include<stdbool.h> #include<stdio.h> typedef int 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;//栈底 //top不是下标 pst->top = 0;//指向栈顶元素的下一个位置 pst->capacity = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; } void STPush(ST* pst,STDataType x) { 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;//返回的是realloc出来的内存块的地址 pst->capacity = newCapacity;//把扩容后的空间大小赋值给栈容量 } pst->a[pst->top] = x;//先放值 pst->top++;//再++ } 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)//栈为空返回true,不为空返回false { //assert(pst); //if (pst->top == 0) //{ // return true; //} //else //{ // return false; //} return pst->top == 0; } int STSize(ST* pst) { assert(pst); return pst->top; }
3.问题题解
s指向的是右括号,top存储的是左括号，st（栈顶指针），a（栈底指针）
- 只要有一次不对应的情况，那么程序直接返回false
- 字符串遍历结束，若栈不为空，直接返回false
- 在比较过程中，若遇到栈为空，可是此时字符串未遍历完，直接返回false
第一种情况:左括号多余
第二种情况:括号没有多余，但是类型匹配不上
第三种情况:右括号多余
代码实现：
bool isValid(char * s){ ST st; STInit(&st); while(*s)//*s就是输入的那个x的值 { //1.左括号入栈 if(*s == '(' || *s == '[' || *s == '{') { STPush(&st, *s); } else { if(STEmpty(&st))//栈为空也需要销毁，因为它malloc了空间，空间在那占用着，只是数据没填进去 { STDestroy(&st); return false; } //右括号出栈匹配 char top=STTop(&st); STPop(&st); //只要有一个不匹配，直接返回false //左括号和右括号相等说明不了问题，只能说明这一次，这一对括号匹配，还有其它括号不匹配的 //所以要找到不继续的条件 if((*s == ']' && top!= '[') ||(*s == ')'&& top !='(') ||(*s=='}' && top!='{')) { STDestroy(&st); return false; } } ++s;//字符指针的移动 } bool ret=STEmpty(&st);//栈不为空那就是false STDestroy(&st); return ret; }
代码执行：
本文结束，若有错误，欢迎改正，谢谢支持！
