【数据结构与算法 经典例题】括号匹配问题
💓 博客主页:倔强的石头的CSDN主页
📝Gitee主页:倔强的石头的gitee主页
⏩ 文章专栏:《数据结构与算法 经典例题》C语言
期待您的关注
目录
一、问题描述
二、解题思路
🍃破解之道
🍃画图举例说明:
三、C语言实现代码
一、问题描述
原题来自
20. 有效的括号 - 力扣(LeetCode)
二、解题思路
🍃破解之道
括号匹配问题是一个比较有实际意义的问题,
问题要求将三种类型括号匹配,其中包括顺序匹配和数量匹配
使用栈的后进先出结构可以很好的解决这个问题:
遍历字符串
遇到左括号则压栈等待右括号匹配;
遇到右括号先进行判断,首先判断栈是否为空,如果为空则不可能完成匹配,直接判定无效
上述判定不成立再进行下列判断
如果此时栈顶的数据是与右括号匹配的左括号,则出栈,否则直接判定无效(顺序不匹配)
当字符串遍历完成时,如果栈为空,则说明括号全部匹配上了;否则说明数量不匹配
关于栈的问题可以阅读前置文章
【数据结构/C语言】使用数组实现栈:原理、步骤与应用-CSDN博客
🍃画图举例说明:
第一种情况:数量顺序完全匹配时
第二种情况:数量匹配,顺序不匹配时
第三种情况:数量不匹配时
三、C语言实现代码
C语言需要自己实现栈的数据结构,轮子之前已经造好了,这里就直接CV拿过来了
#include<stdio.h>
#include<stdlib.h>
#include<assert.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;
}
相关文章:

【数据结构与算法 经典例题】括号匹配问题
💓 博客主页:倔强的石头的CSDN主页 📝Gitee主页:倔强的石头的gitee主页 ⏩ 文章专栏:《数据结构与算法 经典例题》C语言 期待您的关注 目录 一、问题描述 二、解题思路 🍃破解之道 🍃…...

2024年6月最新开源电视影视TVAPP原生源码和后台管理平台源码及完整教程
本套源码为本人维护更新完善半年左右的还在使用开发的源码,与市面上倒卖的残次品不一样,没有可比性,向下兼容安卓4.0,向上兼容安卓13以上TV电视系统, 完全无闪退,弹窗报错,卡死、异常死循环残次…...

[大模型]GLM4-9B-chat Lora 微调
本节我们简要介绍如何基于 transformers、peft 等框架,对 LLaMA3-8B-Instruct 模型进行 Lora 微调。Lora 是一种高效微调方法,深入了解其原理可参见博客:知乎|深入浅出 Lora。 这个教程会在同目录下给大家提供一个 nodebook 文件,…...

目标检测算法YOLOv9简介
YOLOv9由Chien-Yao Wang等人于2024年提出,论文名为:《YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information》,论文见:https://arxiv.org/pdf/2402.13616 ;源码见: https://github.com/W…...

达梦数据库搭建守护集群
前言 DM 数据守护(Data Watch)是一种集成化的高可用、高性能数据库解决方案,是数据库异地容灾的首选方案。通过部署 DM 数据守护,可以在硬件故障(如磁盘损坏)、自然灾害(地震、火灾)…...

OpenGL-ES 学习(6)---- Ubuntu OES 环境搭建
OpenGL-ES Ubuntu 环境搭建 此的方法在 ubuntu 和 deepin 上验证都可以成功搭建 目录 OpenGL-ES Ubuntu 环境搭建软件包安装第一个三角形基于 glfw 实现基于 X11 实现 软件包安装 sudo apt install libx11-dev sudo apt install libglfw3 libglfw3-dev sudo apt-get install…...

Django学习二:配置mysql,创建model实例,自动创建数据库表,对mysql数据库表已经创建好的进行直接操作和实验。
文章目录 前言一、项目初始化搭建1、创建项目:test_models_django2、创建应用app01 二、配置mysql三、创建model实例,自动创建数据库表1、创建对象User类2、执行命令 四、思考问题(****)1、是否会生成新表呢(答案报错&…...
对象创建的4种模式
1. 工厂模式 这种模式抽象了创建具体对象的过程,用函数来封装以特定接口创建对象的细节 缺点:没有解决对象识别的问题(即怎样知道一个对象的类型) function createPerson(name, age, job) {var o new Object();o.name name;o.ag…...
如何判断 是否 需要 CSS 中的媒体查询
以下是一些常见的使用媒体查询的场景: 响应式布局:当设备的屏幕尺寸变化时,我们可以使用媒体查询来调整布局,以适应不同的屏幕尺寸。 设备特性适配:我们可以使用媒体查询来检测设备的特性,如设备方向、分辨…...

设计模式-装饰器模式(结构型)
装饰器模式 装饰器模式是一种结构模式,通过装饰器模式可以在不改变原有类结构的情况下向一个新对象添加新功能,是现有类的包装。 图解 角色 抽象组件:定义组件的抽象方法具体组件:实现组件的抽象方法抽象装饰器:实现…...

升级HarmonyOS 4.2,开启健康生活篇章
夏日来临,华为智能手表携 HarmonyOS 4.2 版本邀您体验,它不仅可以作为时尚单品搭配夏日绚丽服饰,还能充当你的健康管家,从而更了解自己的身体,开启智能健康生活篇章。 高血糖风险评估优化,健康监测更精准 …...
给gRPC增加负载均衡功能
在现代的分布式系统中,负载均衡是确保服务高可用性和性能的关键技术之一。而gRPC作为一种高性能的RPC框架,自然也支持负载均衡功能。本文将探讨如何为gRPC服务增加负载均衡功能,从而提高系统的性能和可扩展性。 什么是负载均衡? …...

【优选算法】详解target类求和问题(附总结)
目录 1.两数求和 题目: 算法思路: 代码: 2.!!!三数之和 题目 算法思路: 代码: 3.四数字和 题目: 算法思路: 代码: 总结&易错点&…...

【数据结构】图论入门
引入 数据的逻辑结构: 集合:数据元素间除“同属于一个集合”外,无其他关系线性结构:一个对一个,例如:线性表、栈、队列树形结构:一个对多个,例如:树图形结构࿱…...
11_1 Linux NFS服务与触发挂载autofs
11_1 Linux NFS服务与触发挂载服务 文章目录 11_1 Linux NFS服务与触发挂载服务[toc]1. NFS服务基础1.1 示例 2. 触发挂载autofs2.1 触发挂载基础2.2 触发挂载进阶autofs与NFS 文件共享服务:scp、FTP、web(httpd)、NFS 1. NFS服务基础 Netwo…...

开发uniapp 小程序时遇到的问题
1、【微信开发者工具报错】routeDone with a webviewId XXX that is not the current page 解决方案: 在app.json 中添加 “lazyCodeLoading”: “requiredComponents” uniapp的话加到manifest.json下的mp-weixin 外部链接文章:解决方案文章1 解决方案文章2 &qu…...

怎样快速获取Vmware VCP 证书,线上考试,voucher报名优惠
之前考一个VCP证书,要花大一万的费用,可贵了,考试费不贵,贵就贵在培训费,要拿到证书,必须交培训费,即使vmware你玩的很溜,不需要再培训了,但是一笔贵到肉疼的培训费你得拿…...
LeetCode 1141, 134, 142
目录 1141. 查询近30天活跃用户数题目链接表要求知识点思路代码 134. 加油站题目链接标签普通版思路代码 简化版思路代码 142. 环形链表 II题目链接标签思路代码 1141. 查询近30天活跃用户数 题目链接 1141. 查询近30天活跃用户数 表 表Activity的字段为user_id,…...
华为FPGA工程师面试题
FPGA工程师面试会涉及多个方面,包括基础知识、项目经验、编程能力、硬件调试和分析等。以下是一些必问的面试题: 基础知识题: 请解释FPGA的基本组成和工作原理。描述FPGA中的可编程互联资源以及它们在构建复杂数字电路中的作用。请解释嵌入式多用途块(如BRAM、DSP slices、…...

Windows11上安装docker(WSL2后端)和使用docker安装MySQL和达梦数据库
Windows11上安装docker(WSL2后端)和使用docker安装MySQL和达梦数据库 1. 操作系统环境2. 首先安装wsl2.1 关于wsl2.2 安装wsl2.3 查看可用的wsl2.4 安装ubuntu-22.042.5 查看、启动ubuntu-22.04应用2.6 上面安装开了daili2.7 wsl的更多参考 3. 下载Docke…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...

STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...