做我的世界皮肤壁纸的网站,wordpress自定义字段怎么用,东莞沙田门户网站建设,自建企业网站模板下载#x1f493; 博客主页#xff1a;倔强的石头的CSDN主页 #x1f4dd;Gitee主页#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏#xff1a;《数据结构与算法 经典例题》C语言 期待您的关注
目录
一、问题描述
二、解题思路
#x1f343;破解之道 #x1f343;… 博客主页倔强的石头的CSDN主页 Gitee主页倔强的石头的gitee主页 ⏩ 文章专栏《数据结构与算法 经典例题》C语言 期待您的关注
目录
一、问题描述
二、解题思路
破解之道 画图举例说明
三、C语言实现代码 一、问题描述 原题来自 20. 有效的括号 - 力扣LeetCode 二、解题思路
破解之道 括号匹配问题是一个比较有实际意义的问题 问题要求将三种类型括号匹配其中包括顺序匹配和数量匹配 使用栈的后进先出结构可以很好的解决这个问题:遍历字符串 遇到左括号则压栈等待右括号匹配 遇到右括号先进行判断首先判断栈是否为空如果为空则不可能完成匹配直接判定无效 上述判定不成立再进行下列判断 如果此时栈顶的数据是与右括号匹配的左括号则出栈否则直接判定无效顺序不匹配 当字符串遍历完成时如果栈为空则说明括号全部匹配上了否则说明数量不匹配 关于栈的问题可以阅读前置文章 【数据结构/C语言】使用数组实现栈原理、步骤与应用-CSDN博客 画图举例说明
第一种情况数量顺序完全匹配时 第二种情况数量匹配顺序不匹配时 第三种情况数量不匹配时 三、C语言实现代码
C语言需要自己实现栈的数据结构轮子之前已经造好了这里就直接CV拿过来了
#includestdio.h
#includestdlib.h
#includeassert.h// 支持动态增长的栈
typedef char STDataType;//对数据类型重命名方便后期修改类型
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack;//定义结构同时重命名// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-a NULL;ps-top ps-capacity 0;
}// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);//判断是否需要扩容if (ps-top ps-capacity){int newcapa ps-capacity 0 ? 4 : 2 * (ps-capacity);STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newcapa);if (tmp NULL){perror(realloc\n);exit(1);}ps-a tmp;ps-capacity newcapa;}//确定空间足够之后再插入数据ps-a[ps-top] data;ps-top;
}// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps-top);ps-top--;
}// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-top);return ps-a[ps-top-1];
}// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;
}// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
}// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}//括号匹配问题
bool isValid(char* s)
{Stack st;StackInit(st);//创建一个栈的结构体变量char* p s;while (*p){if (*p ( || *p [ || *p {)//左括号入栈{StackPush(st,*p);}if (*p ) || *p ] || *p })//右括号进行判断{if (StackEmpty(st))//此时栈空可直接判定false{StackDestroy(st);return false;}else{char tmp StackTop(st);StackPop(st);//栈顶元素出栈if ((*p ) tmp ! ( )//判断顺序是否匹配|| (*p ] tmp ! [ )|| (*p } tmp ! {))return false;}}p;}if (StackEmpty(st))//判断数量是否匹配return true;elsereturn false;
}
