leetcode:有效的括号

题目描述

题目链接:20. 有效的括号 - 力扣(LeetCode)

题目分析

题目给了我们三种括号:()、{ }、[ ]

这里的匹配包括:顺序匹配数量匹配

最优的思路就是用栈来解决:

括号依次入栈,当遇到右括号的时候,和他最近的那个左括号匹配,能匹配则返回true,否则false;最近的左括号即为栈顶元素

数组栈我们在之前实现过,直接拿来用就可以了:数组栈的实现-CSDN博客

由于存放的数据是字符,所以这里的STDataType就可以typedef为char

遍历字符串:

  • 是左括号就入栈
  • 遇到右括号,则取栈顶元素,并pop掉
  • 最后如果栈为空则返回true,否则返回false,所以我们还需要判空
  • 防止内存泄漏,我们在每次返回false之前都需要Destroy

代码示例

根据这个思路我们就可以写代码了:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;//标识栈顶位置int capacity;
}ST;
//声明//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//返回栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//栈的元素个数
int STSize(ST* pst);//定义//初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}
//销毁
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}
//入栈
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}
//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}
//返回栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{assert(pst);/*if (pst->top == 0){return true;}else{return false;}*/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;}//取栈顶元素char top = STTop(&st);STPop(&st);//匹配if ((*s == ')' && top != '(') || (*s == ']' && top != '[') || (*s == '}' && top != '{')){STDestroy(&st);return false;}}++s;}bool ret = STEmpty(&st);STDestroy(&st);return ret;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/204267.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

用于计算机屏幕安全摄像头系统:Screen Anytime Crack

Screen Anytime 是一款软件&#xff0c;旨在自动将整个用户会话或 PC/服务器/VM/Kiosk 的 /RDP/Citrix/RemoteApp 会话的屏幕活动记录到视频日志文件中&#xff0c;以用于记录、审核和监控目的。通过重播其高度压缩的视频&#xff0c;您可以轻松回顾单台计算机或一组服务器/PC …

Joint Bilateral Upsampling

Abstract 图像分析和增强任务&#xff08;例如色调映射、着色、立体深度和蒙太奇&#xff09;通常需要在像素网格上计算解决方案&#xff08;例如&#xff0c;曝光、色度、视差、标签&#xff09;。计算和内存成本通常要求在下采样图像上运行较小的解决方案。尽管通用上采样方…

只需十分钟快速入门Python,快速了解基础内容学习。零基础小白入门适用。

文章目录 简介特点搭建开发环境版本hello world注释文件类型变量常量数据类型运算符和表达式控制语句数组相关函数相关字符串相关文件处理对象和类连接mysql关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品Python学习书籍四、Python工具包项目源…

matlab绘图函数plot和fplot的区别

一、背景 有的函数用plot画就会报错&#xff0c;显示数据必须为可转换为双精度值的数值、日期时间、持续时间、分类或数组。 如下图所示&#xff1a; 但用fplot函数就没有问题&#xff0c;因此这里记录一下两者的区别&#xff0c;如果使用不当&#xff0c;画出的图可能就是下…

以太网通讯协议小结--持续更新中

一、以太网介绍 以太网是一种产生较早&#xff0c;使用相当广泛的局域网技术&#xff0c;局域网就是一个区域的网络互联&#xff0c;可以使办公室也可以是学校等等&#xff0c;大小规模不一。 目前以太网根据速度等级分类大概分为&#xff1a;标准以太网&#xff08;10Mbit/s…

Redis-Redis高可用集群之水平扩展

Redis3.0以后的版本虽然有了集群功能&#xff0c;提供了比之前版本的哨兵模式更高的性能与可用性&#xff0c;但是集群的水平扩展却比较麻烦&#xff0c;今天就来带大家看看redis高可用集群如何做水平扩展&#xff0c;原始集群(见下图)由6个节点组成&#xff0c;6个节点分布在三…

JOSEF 双可调漏电继电器 ZLR-T81 ZCT-80 面板嵌入式安装

ZLR-T系列漏电继电器&#xff08;以下简称继电器&#xff09;适用于交流电压为380.660V.至1140V系统中源率为50HZ电流为15~4000A线路中做有无中性点漏电保护. 系列型号 ZLR-T81漏电继电器 ZLR-T81ZCT-35漏电继电器 ZLR-T81ZCT-80漏电继电器 ZLR-T81ZCT-120漏电继电器 一、…

csv文件EXCEL默认打开乱码问题

这里讨论的问题是&#xff0c;当用记事本打开带有中文字符的csv正常时&#xff0c;用excel打开却是乱码。 简单概括就是&#xff1a;编码问题&#xff0c;windows的 excel打开csv文本文件时&#xff0c;默认使用的是系统内的ANSI&#xff0c;在中文环境下就是GB2312。如果写文件…

华为ospf和isis双点双向路由重分布的次优路径和环路终极解决方案

r5上直接导入直连路由 r3和r2进行双点双向路由重分布 查看R3去往R5产生了次优路径&#xff1a; 因为是R2先互相引入的isis和ospf&#xff0c;所以R3会产生次优路径&#xff0c;如果是R3先相互引入ospf和isis&#xff0c;那就是R2去R5会产生次优路径&#xff0c;而R3本身不会。…

Spark_Spark高阶特性

wscg filter导致断链 Codegen 向量化 simdjson Orc Parquet 支持批量读取 spark本身对parquet支持比较好&#xff0c;因为parquet

基于FPGA的五子棋游戏设计

基于FPGA的五子棋游戏设计 本文基于FPGA设计五子棋游戏&#xff0c;使用按键输入&#xff0c;使用VGA接口输出。五子棋的棋具与围棋相同&#xff0c;棋子分为黑白两色&#xff0c;棋盘为1010&#xff0c;棋子放置于棋盘线交叉点上。两人对局&#xff0c;各执一色&#xff0c;轮…

牛客 算法题 golang语言实现

题目 HJ101 输入整型数组和排序标识&#xff0c;对其元素按照升序或降序进行排序 描述 输入整型数组和排序标识&#xff0c;对其元素按照升序或降序进行排序数据范围&#xff1a; 1 ≤ &#xfffd; ≤ 10001≤n≤1000 &#xff0c;元素大小满足 0 ≤ &#xfffd; &#…

有一种浪漫,叫接触Linux

大家好&#xff0c;我是五月。 嵌入式开发 嵌入式开发产品必须依赖硬件和软件。 硬件一般使用51单片机&#xff0c;STM32、ARM&#xff0c;做成的产品以平板&#xff0c;手机&#xff0c;智能机器人&#xff0c;智能小车居多。 软件用的当然是以linux系统为蓝本&#xff0c…

五分钟 k8s 实战-应用探针

Probe.png 今天进入 kubernetes 的运维部分&#xff08;并不是运维 kubernetes&#xff0c;而是运维应用&#xff09;&#xff0c;其实日常我们大部分使用 kubernetes 的功能就是以往运维的工作&#xff0c;现在云原生将运维和研发关系变得更紧密了。 今天主要讲解 Probe 探针相…

SpringCloud 微服务全栈体系(十七)

第十一章 分布式搜索引擎 elasticsearch 七、搜索结果处理 搜索的结果可以按照用户指定的方式去处理或展示。 1. 排序 elasticsearch 默认是根据相关度算分&#xff08;_score&#xff09;来排序&#xff0c;但是也支持自定义方式对搜索结果排序。可以排序字段类型有&#…

C语言进阶指南(11)(指针数组与二维数组)

*欢迎来到博主的专栏——C语言进阶指南 博主id&#xff1a;reverie_ly 文章目录 N级指针指针数组指针数组与二维数组数组指针作为函数的参数 N级指针 指针变量是一个存放地址的变量&#xff0c;在C语言中&#xff0c;每个变量都会有一个地址值。所以指针变量也有一个地址。 …

WIN10 x86环境部署ARM虚拟机(银河麒麟)

我们经常使用的是x86架构的cpu&#xff0c;而对于不同cpu架构的arm架构的操作系统&#xff0c;我们可以通过QEMU模拟器来进行模拟一个arm环境 1、部署前的准备 arm的镜像&#xff1a; 以此镜像为例&#xff1a;Kylin-Server-10-SP2-aarch64-Release-Build09-20210524.iso QE…

【C++ Primer Plus学习记录】while循环

while循环是没有初始化和更新部分的for循环&#xff0c;它只有测试条件和循环体&#xff1a; while(test-condition)dody 首先&#xff0c;程序计算圆括号内的测试条件表达式。如果该表达式为true&#xff0c;则执行循环体内的语句。与for循环一样&#xff0c;循环体也由一条…

IO和NIO的区别 BIO,NIO,AIO 有什么区别? Files的常用方法都有哪些?

文章目录 IO和NIO的区别BIO,NIO,AIO 有什么区别?Files的常用方法都有哪些&#xff1f; 今天来对java中的io, nio, bio, aio进行了解&#xff0c;有何区别。 IO和NIO的区别 NIO与IO区别 IO是面向流的&#xff0c;NIO是面向缓冲区的Java IO面向流意味着每次从流中读一个或多个字…

数据结构-单链表

文章目录 单链表概念链接存储方法头指针head和终端结点链接过程单链表的优缺点&#xff1a;实现代码一览 单链表概念 链表中的数据是以结点来表示的&#xff0c;每个结点的构成&#xff1a;元素(数据元素的映象) 指针(指示后继元素存储位置)&#xff0c;元素就是存储数据的存储…