【数据结构算法经典题目刨析(c语言)】括号匹配问题(图文详解)
💓 博客主页:C-SDN花园GGbond
⏩ 文章专栏:数据结构经典题目刨析(c语言)
目录
一、题目描述
二、解题思路
三、代码实现
一、题目描述

二、解题思路
问题要求将三种类型括号匹配,其中包括顺序匹配和数量匹配
使用栈的后进先出结构可以很好的解决这个问题:
根据栈独有的特点,具体操作:1、属于左括号,进行入栈处理。2、属于右括号进行出栈处理,然后进行匹配,不匹配就报错。我们既然选择用C语言来实现,就需要我们自己提前实现一个栈结构
先实现栈 :
//栈的初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->top = pst->capacity = 0;//top指向栈顶元素的下一个位置}
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;}
void STPush(ST* pst, STDatyType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity=pst->capacity==0 ? 4 : pst->capacity * 2;STDatyType* tmp =(STDatyType*)realloc(pst->a, newcapacity * sizeof(STDatyType));if (tmp == NULL){perror("ralloc fail");return;}pst->capacity = newcapacity;pst->a = tmp;}pst->a[pst->top] = x;pst->top++;
}
//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}
//得到栈顶元素
STDatyType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}
//获取数据个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}
遍历字符串
遇到左括号则压栈等待右括号匹配;
遇到右括号先进行判断,首先判断栈是否为空,如果为空则不可能完成匹配,直接判定无效
上述判定不成立再进行下列判断
如果此时栈顶的数据是与右括号匹配的左括号,则出栈,否则直接判定无效(顺序不匹配)
当字符串遍历完成时,如果栈为空,则说明括号全部匹配上了;否则说明数量不匹配
画图举例说明:
第一种情况:数量顺序完全匹配时

第二种情况:数量匹配,顺序不匹配时
第三种情况:数量不匹配时
三、代码实现
typedef char STDatyType;
typedef struct Stack
{STDatyType* a;int top;int capacity;}ST;
//栈的初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->top = pst->capacity = 0;//top指向栈顶元素的下一个位置}
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;}
void STPush(ST* pst, STDatyType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity=pst->capacity==0 ? 4 : pst->capacity * 2;STDatyType* tmp =(STDatyType*)realloc(pst->a, newcapacity * sizeof(STDatyType));if (tmp == NULL){perror("ralloc fail");return;}pst->capacity = newcapacity;pst->a = tmp;}pst->a[pst->top] = x;pst->top++;
}
//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}
//得到栈顶元素
STDatyType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}
//获取数据个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}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;}//栈不为空STDatyType top=STTop(&st);if(*s==')'&&top!='('||*s==']'&&top!='['||*s=='}'&&top!='{'){STDestroy(&st);return false;}//匹配然后出栈STPop(&st);}s++;}if(STEmpty(&st)){STDestroy(&st);return true;}else{STDestroy(&st);return false;}
}
相关文章:
【数据结构算法经典题目刨析(c语言)】括号匹配问题(图文详解)
💓 博客主页:C-SDN花园GGbond ⏩ 文章专栏:数据结构经典题目刨析(c语言) 目录 一、题目描述 二、解题思路 三、代码实现 一、题目描述 二、解题思路 问题要求将三种类型括号匹配,其中包括顺序匹配和数量匹配 使用栈的后进先…...
浅谈 Spring AOP框架 (1)
文章目录 一、什么是 Spring AOP二、为什么要使用 Spring AOP三、AOP 的一些应用场景四、AOP 的组成五、如何使用 Spring AOP六、Spring AOP 的实现原理6.1、JDK 和 CGLIB 的区别 一、什么是 Spring AOP AOP (Aspect Oriented Programming) :面向切面编程ÿ…...
Linux 面试准备 - 2024
复习一下,资料来自慕课网课程 Linux 速成班和一些网上面试资料。 1. Linux 内核功能 1. 内存管理 2. 进程管理 3. 设备驱动程序 4. 系统调用和安全防护 2. 文件系统 - 一切皆文件 2.1 文件目录 /根目录etc配置文件bin必要命令usr 二级目录(非用户…...
C++笔记---类和对象(中)
1. 类的默认成员函数 默认成员函数就是用户没有显式实现,编译器会自动生成的成员函数称为默认成员函数。 一个类,我们不写的情况下编译器会默认生成以下6个默认成员函数,分别为:构造函数,析构函数,拷贝构…...
【C++】入门基础知识
河流之所以能够到达目的地,是因为它懂得怎样避开障碍。💓💓💓 目录 ✨说在前面 🍋知识点一:C的发展历史 • 🌰1.C发展历史 • 🌰2.C的迭代与更新 • 🌰3.编程语言排…...
AI的应用场景和未来展望
AI(人工智能)的应用场景广泛且多样,已经深入到我们生活的方方面面,成为现代社会不可或缺的一部分。 AI的应用场景 1、通用软件与工具型应用 办公软件:如钉钉、飞书等,通过AI技术提供内容生成与摘要、智能…...
vim、sublime、notepad文本编辑器的使用
VIM: Windows上配置gvim并作为C和C的IDE Windows上配置gvim并作为C和C的IDE | Reasuon sublime notepad...
PyCharm中的外部更改识别:终极解决方案指南
标题:PyCharm中的外部更改识别:终极解决方案指南 引言 PyCharm,作为JetBrains公司开发的集成开发环境(IDE),以其强大的功能和高效的代码编辑体验而广受开发者喜爱。然而,在开发过程中…...
Qt——QTCreater ui界面如何统一设置字体
第一步:来到 ui 设计界面,鼠标右键点击 改变样式表 第二步:选择添加字体 第三步:选择字体样式和大小,点击 ok 第四步:点击ok或apply,完成设置...
Linux驱动入门实验班day03-GPIO子系统概述
3.通用框架1——最简单方式1:执行命令cat /sys/kernel/debug/gpio查看串口信息 gpio4对应的下列 方式2: 对于按键GPIO4_14:对应第四组第14个引脚 gpiochip3 ,从96开始, 9614110;...
240803-沉侵式翻译插件配置Ollama的API实现网页及PDF文档的翻译
1. 在插件中点击Options按钮 2. 在开发者模式中启动Enable Beta Testing Features 3 在General中进行设置 ## 4. 在Expand中设置API的URL 5. Qwen:0.5B网页翻译效果 6. Qwen:0.5BPDF翻译效果 7. 参考文献 gemma - 给沉浸式翻译插件配置本地大模型o…...
HTML-08.表单标签
一.表单标签 场景:在网页中主要负责数据采集功能,如注册、登录等数据采集 标签:<form> 表单项:不同类型的input元素、下拉列表、文本域等 <input>:定义表单项。通过type属性控制输入形式 <select>:定义下拉列表…...
SAP ABAP se16n 双击跳转实现
参考老白 SAP小技巧 改造SE16N(九 双击跳转及字段描述优化) (qq.com) se16n 双击跳转实现 我的实现 se38 lse16nlcl 287行 call method cl_gui_control>set_focusexporting control alv_grid. *.....at the moment do detail view on double clickCALL METHOD cl_gu…...
Linux shell编程学习笔记68: curl 命令行网络数据传输工具 选项数量雷人(上)
0 前言 在网络时代,有经常需要在网络上传输数据,时我们需要通过网络下载文件,为了满足这种时代需要,Linux提供了众多网络命令,我们今天先研究curl命令。例如,我们可以使用 curl 从 URL 下载文件࿰…...
马尔科夫决策过程
马尔科夫决策过程 贝尔曼方程 贝尔曼方程(Bellman Equation)是动态规划中的一个核心概念,用于解决最优决策问题。贝尔曼方程通过递归的方式,将问题分解为子问题,从而使得最优策略的求解变得可行。贝尔曼方程广泛应用…...
未知攻焉知防:从攻击者视角看网络安全的“攻守之道”
自首届网络安全攻防实战演练开展以来,这一活动已成为网络安全领域备受关注的大事件。今年,攻防实战演练更上升到了一个全新高度,包括行动任务数量、演练周期时长、攻击强度以及演练类别等,较以往都有极大提升,堪称“史…...
数字孪生赋能智慧城市大脑智建设方案(可编辑65页PPT)
引言:随着科技的飞速发展,智慧城市的建设已成为全球城市发展的新趋势。数字孪生技术作为其中的关键技术之一,正逐步赋能智慧城市大脑的建设,推动城市治理从数字化向智能化、智慧化转型升级。本方案旨在简要介绍数字孪生赋能智慧城…...
c++----内存管理
okk,大家好。我们大家学习了鄙人的前面前面几篇博客,并且还稍微使用了一些c的基础知识。并且我们前面都说过,我们前面学习的知识都说过。我们前面的几篇博客都是我们以后使用c基础。但是我们大家都知道现在代码都关注什么时间啊,内…...
C++——哈希结构
1.unordered系列关联式容器 本节主要介绍unordered_map和unordered_set两个容器,底层使用哈希实现的 unordered_map 1.unordered_map是储存<key,value>键值对的关联式容器,其允许通过key快速查找到对应的value,和map非常相似&#x…...
智能小程序 Ray 开发面板 SDK —— 无线开关一键执行模板教程(一)
1. 准备工作 前提条件 已阅读 Ray 新手村任务,了解 Ray 框架的基础知识已阅读 使用 Ray 开发万能面板,了解 Ray 面板开发的基础知识 构建内容 在此 Codelab 中,您将利用面板小程序开发构建出一个支持一键执行及自动化的无线开关面板&…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道
文/法律实务观察组 在债务重组领域,专业机构的核心价值不仅在于减轻债务数字,更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明,合法债务优化需同步实现三重平衡: 法律刚性(债…...
前端工具库lodash与lodash-es区别详解
lodash 和 lodash-es 是同一工具库的两个不同版本,核心功能完全一致,主要区别在于模块化格式和优化方式,适合不同的开发环境。以下是详细对比: 1. 模块化格式 lodash 使用 CommonJS 模块格式(require/module.exports&a…...
Qt的学习(二)
1. 创建Hello Word 两种方式,实现helloworld: 1.通过图形化的方式,在界面上创建出一个控件,显示helloworld 2.通过纯代码的方式,通过编写代码,在界面上创建控件, 显示hello world; …...
