当前位置: 首页 > news >正文

【数据结构与算法 经典例题】括号匹配问题

             💓 博客主页:倔强的石头的CSDN主页 

             📝Gitee主页:倔强的石头的gitee主页

   ⏩ 文章专栏:《数据结构与算法 经典例题》C语言

                                  期待您的关注

1b7335aca73b41609b7f05d1d366f476.gif​​

目录

一、问题描述

二、解题思路

🍃破解之道

 🍃画图举例说明:

三、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;
}

相关文章:

【数据结构与算法 经典例题】括号匹配问题

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《数据结构与算法 经典例题》C语言 期待您的关注 ​​ 目录 一、问题描述 二、解题思路 &#x1f343;破解之道 &#x1f343;…...

2024年6月最新开源电视影视TVAPP原生源码和后台管理平台源码及完整教程

本套源码为本人维护更新完善半年左右的还在使用开发的源码&#xff0c;与市面上倒卖的残次品不一样&#xff0c;没有可比性&#xff0c;向下兼容安卓4.0&#xff0c;向上兼容安卓13以上TV电视系统&#xff0c; 完全无闪退&#xff0c;弹窗报错&#xff0c;卡死、异常死循环残次…...

[大模型]GLM4-9B-chat Lora 微调

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

目标检测算法YOLOv9简介

YOLOv9由Chien-Yao Wang等人于2024年提出&#xff0c;论文名为&#xff1a;《YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information》&#xff0c;论文见&#xff1a;https://arxiv.org/pdf/2402.13616 &#xff1b;源码见: https://github.com/W…...

达梦数据库搭建守护集群

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

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、创建项目&#xff1a;test_models_django2、创建应用app01 二、配置mysql三、创建model实例&#xff0c;自动创建数据库表1、创建对象User类2、执行命令 四、思考问题&#xff08;****&#xff09;1、是否会生成新表呢&#xff08;答案报错&…...

对象创建的4种模式

1. 工厂模式 这种模式抽象了创建具体对象的过程&#xff0c;用函数来封装以特定接口创建对象的细节 缺点&#xff1a;没有解决对象识别的问题&#xff08;即怎样知道一个对象的类型&#xff09; function createPerson(name, age, job) {var o new Object();o.name name;o.ag…...

如何判断 是否 需要 CSS 中的媒体查询

以下是一些常见的使用媒体查询的场景&#xff1a; 响应式布局&#xff1a;当设备的屏幕尺寸变化时&#xff0c;我们可以使用媒体查询来调整布局&#xff0c;以适应不同的屏幕尺寸。 设备特性适配&#xff1a;我们可以使用媒体查询来检测设备的特性&#xff0c;如设备方向、分辨…...

设计模式-装饰器模式(结构型)

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

升级HarmonyOS 4.2,开启健康生活篇章

夏日来临&#xff0c;华为智能手表携 HarmonyOS 4.2 版本邀您体验&#xff0c;它不仅可以作为时尚单品搭配夏日绚丽服饰&#xff0c;还能充当你的健康管家&#xff0c;从而更了解自己的身体&#xff0c;开启智能健康生活篇章。 高血糖风险评估优化&#xff0c;健康监测更精准 …...

给gRPC增加负载均衡功能

在现代的分布式系统中&#xff0c;负载均衡是确保服务高可用性和性能的关键技术之一。而gRPC作为一种高性能的RPC框架&#xff0c;自然也支持负载均衡功能。本文将探讨如何为gRPC服务增加负载均衡功能&#xff0c;从而提高系统的性能和可扩展性。 什么是负载均衡&#xff1f; …...

【优选算法】详解target类求和问题(附总结)

目录 1.两数求和 题目&#xff1a; 算法思路&#xff1a; 代码&#xff1a; 2.&#xff01;&#xff01;&#xff01;三数之和 题目 算法思路&#xff1a; 代码&#xff1a; 3.四数字和 题目&#xff1a; 算法思路&#xff1a; 代码&#xff1a; 总结&易错点&…...

【数据结构】图论入门

引入 数据的逻辑结构&#xff1a; 集合&#xff1a;数据元素间除“同属于一个集合”外&#xff0c;无其他关系线性结构&#xff1a;一个对一个&#xff0c;例如&#xff1a;线性表、栈、队列树形结构&#xff1a;一个对多个&#xff0c;例如&#xff1a;树图形结构&#xff1…...

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 文件共享服务&#xff1a;scp、FTP、web&#xff08;httpd&#xff09;、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 外部链接文章&#xff1a;解决方案文章1 解决方案文章2 &qu…...

怎样快速获取Vmware VCP 证书,线上考试,voucher报名优惠

之前考一个VCP证书&#xff0c;要花大一万的费用&#xff0c;可贵了&#xff0c;考试费不贵&#xff0c;贵就贵在培训费&#xff0c;要拿到证书&#xff0c;必须交培训费&#xff0c;即使vmware你玩的很溜&#xff0c;不需要再培训了&#xff0c;但是一笔贵到肉疼的培训费你得拿…...

LeetCode 1141, 134, 142

目录 1141. 查询近30天活跃用户数题目链接表要求知识点思路代码 134. 加油站题目链接标签普通版思路代码 简化版思路代码 142. 环形链表 II题目链接标签思路代码 1141. 查询近30天活跃用户数 题目链接 1141. 查询近30天活跃用户数 表 表Activity的字段为user_id&#xff0c…...

华为FPGA工程师面试题

FPGA工程师面试会涉及多个方面,包括基础知识、项目经验、编程能力、硬件调试和分析等。以下是一些必问的面试题: 基础知识题: 请解释FPGA的基本组成和工作原理。描述FPGA中的可编程互联资源以及它们在构建复杂数字电路中的作用。请解释嵌入式多用途块(如BRAM、DSP slices、…...

Windows11上安装docker(WSL2后端)和使用docker安装MySQL和达梦数据库

Windows11上安装docker&#xff08;WSL2后端&#xff09;和使用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…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

python读取SQLite表个并生成pdf文件

代码用于创建含50列的SQLite数据库并插入500行随机浮点数据&#xff0c;随后读取数据&#xff0c;通过ReportLab生成横向PDF表格&#xff0c;包含格式化&#xff08;两位小数&#xff09;及表头、网格线等美观样式。 # 导入所需库 import sqlite3 # 用于操作…...

window 显示驱动开发-如何查询视频处理功能(三)

​D3DDDICAPS_GETPROCAMPRANGE请求类型 UMD 返回指向 DXVADDI_VALUERANGE 结构的指针&#xff0c;该结构包含特定视频流上特定 ProcAmp 控件属性允许的值范围。 Direct3D 运行时在D3DDDIARG_GETCAPS的 pInfo 成员指向的变量中为特定视频流的 ProcAmp 控件属性指定DXVADDI_QUER…...

SOC-ESP32S3部分:30-I2S音频-麦克风扬声器驱动

飞书文档https://x509p6c8to.feishu.cn/wiki/SKZzwIRH3i7lsckUOlzcuJsdnVf I2S简介 I2S&#xff08;Inter-Integrated Circuit Sound&#xff09;是一种用于传输数字音频数据的通信协议&#xff0c;广泛应用于音频设备中。 ESP32-S3 包含 2 个 I2S 外设&#xff0c;通过配置…...