当前位置: 首页 > 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…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...