【数据结构算法经典题目刨析(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 中,您将利用面板小程序开发构建出一个支持一键执行及自动化的无线开关面板&…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
