您现在的位置是:首页 >技术教程 >【力扣-20】有效的括号网站首页技术教程
【力扣-20】有效的括号
简介【力扣-20】有效的括号
🖊作者 : D. Star.
📘专栏 : 数据结构
😆今日分享 : 夏虫不可以语冰 : 出自「庄子·秋水」。原句是“井蛙不可以语于海者,拘于虚也;夏虫不可以语于冰者,笃于时也;曲士不可以语于道者,束于教也”。而这句话的意思就是,一种虫子如果它生命周期只有夏天这几个月,你跟它说冰是什么东西,它是不会知道的,它想象不出来那个东西,因为它的生命周期从来不经过冬天。
这句话常常用来比喻时间局限人的见识,也比喻人的见识短浅,不懂大道理。
文章目录
🌻题目链接:
🌻题目详情:
题目 : 给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例:
🌻解题思路:
解题思路:
循环遍历String中的字符,逐个取到每个括号,如果该括号是:
1. 左括号,直接入栈
2. 右括号,与栈顶的左括号进行匹配,如果不匹配直接返回false
否则继续循环
循环结束后,如果栈空则匹配,否则左括号比右括号多肯定不匹配
🔎代码详情:
#define DataType char
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
typedef struct Stack
{
DataType* a;
int top;
int capacity;
}ST;
//初始化
void stackInit(ST* st)
{
assert(st);//断言st是否是空指针(因为assert不能为空)
st->a = (DataType*)malloc(sizeof(DataType));//1个空间
if (st->a == NULL)
{
perror("malloc fail:");
exit(-1);
}
st->capacity = 1;
st->top = -1;
}
//销毁
void stackDestory(ST* st)
{
assert(st);//断言st是否是空指针(因为assert不能为空)
free(st->a);//注意:这里free的是数组的空间,不是结构体
st->a = NULL;
st->capacity = 0;
st->top = -1;
}
//入栈
void stackPush(ST* st, DataType x)
{
assert(st);//断言st是否是空指针(因为assert不能为空)
//不为空时,入栈
// 判断数组是否满
if (st->top + 1 == st->capacity)
/*if(st->capacity == st->top )*/
{
DataType* tmp = (DataType*)realloc(st->a, 2 * sizeof(DataType) * st->capacity );
//开辟空间失败时,返回
if (tmp == NULL)
{
perror("realloc fail : ");
exit(-1);
}
//成功时,将开辟空间的地址给到st->a
st->a = tmp;
st->capacity *= 2;
}
//尾插
st->top++;
st->a[st->top] = x;
}
//出栈
void stackPop(ST* st)
{
assert(st);
assert(st->top > -1);
//出栈
st->top--;
}
//判断栈是否为空
bool stackEmpty(ST* st)
{
assert(st);
// //法一:
// if (st->top > -1)
// {
// return false;
// }
// else return true;
//法二:
return !(st->top > -1);
}
//获取栈顶元素
DataType stackTop(ST* st)
{
assert(st);
assert(!stackEmpty(st));
return st->a[st->top];
}
bool isValid(char * s){
ST st;
stackInit(&st);//初始化先
while(*s)
{
if((*s == '{') || (*s == '(') || (*s == '['))
{
//如果是左括号,则入栈
stackPush(&st,*s);
s++;
}
else
{
//如果栈为空,即没有左括号与右括号匹配,则false;
if(stackEmpty(&st))
return false;
//如果不是左括号,则提取栈顶元素与当前的元素进行比较是否配对;
if((stackTop(&st) == '(' && *s == ')') ||
(stackTop(&st) == '[' && *s == ']') ||
(stackTop(&st) == '{' && *s == '}'))
{
//如果相等,则进行下一个比较;
s++;
stackPop(&st);
}
else
{
//如果不相等,则false;
return false;
}
}
}
//如果右括号匹配完,左括号还有的话(不为空),也是false;
bool ret = stackEmpty(&st);
stackDestory(&st);
return ret;
}
🌻总结:
- 调用的方法,必须放在该函数前面
- 思路要清晰,知道自己需要哪些变量
感谢家人的阅读,若有不准确的地方 欢迎在评论区指正!
家人们,点个再走呗~
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。