每日一题---OJ题: 有效的括号

片头

嗨! 小伙伴们,大家好! 我们又见面啦! 今天我们来一起尝试一下这道题目---有效的括号,准备好了吗? 我们开始咯!

说实话,我刚开始做这道题的时候也是一脸懵,怎么进行括号匹配呢?

别慌,我们一起画个图,分析分析括号匹配的过程~

如下图所示,上方表示一个字符串数组,存放不同种类的左括号和右括号,用一个指针依次遍历字符串中的每一个元素

如果是左括号,则入栈,如果是右括号,则栈顶元素出栈和字符串数组中的元素进行匹配。

第一次:

左括号,则入栈

第二次:

左括号,则入栈

第三次:

左括号,则入栈

 第四次:

此时指针指向的元素为右括号,应该出栈

第五次:

左括号,则入栈

第六次:

右括号,则出栈

 第七次：

右括号，则出栈

第八次：

右括号，则出栈

第九次：

左括号，则入栈

第十次：

右括号，则出栈

第十一次：

左括号，则入栈

第十二次：

右括号，则出栈

好的，这道题的执行过程我们大致分析清楚了，怎么实现呢？

 我们可以利用栈来解答这道题

先定义Stack.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int ElemType;
typedef struct Stack {
	ElemType* arr;		//数组
	int top;			//栈顶
	int capacity;		//栈的容量
}Stack;

//初始化栈
void StackInit(Stack* ps);
//入栈
void StackPush(Stack* ps,ElemType data);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
ElemType StackTop(Stack* ps);
//获取栈中有效元素的个数
int StackSize(Stack* ps);
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps);
//销毁栈
void StackDestroy(Stack* ps);

 再定义Stack.c文件

#include"Stack.h"
//初始化栈
void StackInit(Stack* ps) {
	assert(ps);
	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//入栈
void StackPush(Stack* ps, ElemType data) {
	assert(ps);
	//扩容
	if (ps->capacity == ps->top) {
		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
		ElemType* temp =(ElemType*) realloc(ps->arr, newCapacity * sizeof(ElemType));
		if (temp == NULL) {
			perror("realloc fail!\n");
			exit(1);
		}
		ps->arr = temp;
		ps->capacity = newCapacity;
	}

	ps->arr[ps->top] = data;
	ps->top++;
}
//出栈
void StackPop(Stack* ps) {
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
//获取栈顶元素
ElemType StackTop(Stack* ps) {
	assert(ps);
	assert(!StackEmpty(ps));
	int ret = ps->arr[ps->top - 1];
	return ret;
}
//获取栈中有效元素的个数
int StackSize(Stack* ps) {
	assert(ps);
	return ps->top;
}
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps) {
	assert(ps);
	return ps->top == 0;	//如果top为0,说明栈为空,返回1
}
//销毁栈
void StackDestroy(Stack* ps) {
	assert(ps);
	if (ps->arr) {
		free(ps->arr);
		ps->arr = NULL;
	}
	ps->capacity = 0;
	ps->top = 0;
}

最后我们再来测试一下,定义test.c文件

#include"Stack.h"
#include<stdbool.h>
int main() {
	Stack st;            //定义一个栈
	StackInit(&st);      //初始化这个栈
	StackPush(&st, 1);   //将"1"放入栈内
	StackPush(&st, 2);   //将"2"放入栈内
	StackPush(&st, 3);   //将"3"放入栈内
	StackPush(&st, 4);   //将"4"放入栈内
	StackPush(&st, 5);   //将"5"放入栈内

	while (!StackEmpty(&st)) {    //如果栈不为空,那么获取栈中的元素
		int top = StackTop(&st);   //获取栈顶元素
		printf("%d ", top);        //打印栈顶元素
		StackPop(&st);            //将栈顶元素删除
	}

	StackDestroy(&st);            //销毁栈
	return 0;
}

运行结果为:

5   4   3   2   1

 OK啦,我们的栈就实现完毕! 接下来我们就可以将它套用到题目中去~

我们刚写了一个栈,直接把 Stack.h 和 Stack.c 复制粘贴过去,把头文件删掉, 再把 typedef int ElemType 改成 typedef char ElemType;

部分代码如下:

typedef char ElemType;        //一定是 char, 不要弄错了,题目要求是字符串数组
typedef struct Stack {
	ElemType* arr;		//数组
	int top;			//栈顶
	int capacity;		//栈的容量
}Stack;

//初始化栈
void StackInit(Stack* ps);
//入栈
void StackPush(Stack* ps,ElemType data);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
ElemType StackTop(Stack* ps);
//获取栈中有效元素的个数
int StackSize(Stack* ps);
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps);
//销毁栈
void StackDestroy(Stack* ps);

//初始化栈
void StackInit(Stack* ps) {
	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//入栈
void StackPush(Stack* ps, ElemType data) {
	//扩容
	if (ps->capacity == ps->top) {
		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
		ElemType* temp =(ElemType*) realloc(ps->arr, newCapacity * sizeof(ElemType));
		if (temp == NULL) {
			perror("realloc fail!\n");
			exit(1);
		}
		ps->arr = temp;
		ps->capacity = newCapacity;
	}

	ps->arr[ps->top] = data;    //插入数据
	ps->top++;                  //栈顶向上移动一个单位
}
//出栈
void StackPop(Stack* ps) {
	assert(ps);
	assert(!StackEmpty(ps));    //栈不能为空
	ps->top--;
}
//获取栈顶元素
ElemType StackTop(Stack* ps) {
	assert(ps);
	assert(!StackEmpty(ps));
    //不改变top指针,只是获取栈顶元素
	int ret = ps->arr[ps->top - 1];
	return ret;
}
//获取栈中有效元素的个数
int StackSize(Stack* ps) {
	assert(ps);
	return ps->top; //top恰好是元素的个数
}
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps) {
	return ps->top == 0;
}
//销毁栈
void StackDestroy(Stack* ps) {
    assert(ps);
	if (ps->arr) {
		free(ps->arr);
		ps->arr = NULL;
	}
	ps->capacity = 0;
	ps->top = 0;
}

 接下来就是重头戏咯! 小伙伴们可要看仔细咯!

第一步,我们先定义一个栈,然后将这个栈初始化

   Stack st;           //定义一个栈
    StackInit(&st);     //初始化这个栈

第二步,我们用题目所给的条件: 该方法传递过来的形参s, 类型为char* ,意味着s是一个指向字符串数组的指针,可以遍历整个字符串数组, 因此,当s指针遍历到字符串数组的结束符'\0'的时候,退出循环。

和刚刚我们分析的思路一样，当s指针遍历到左括号时,则该元素入栈; 当s指针遍历到右括号时,将栈里面的元素出栈,看是否匹配; 如果匹配不成功,直接返回false; 接着,s指针继续指向下一个元素。

这里有一个特别容易被忽略的一个点： 当栈为空，且遇到右括号，栈里面没有左括号，销毁栈,返回false

这个部分的代码如下:

//当*s不等于'\0'的时候,进入while循环
while(*s){

    if(*s == '{' || *s == '[' || *s == '('){
        //将该元素放入栈内
        StackPush(&st,*s);
   }else{
        //当栈为空,且遇到右括号,栈里面没有左括号,返回false
        if(StackEmpty(&st)){
        //销毁栈,防止内存泄漏
            StackDestroy(&st);
           return false;
         }

        int top = StackTop(&st);        //获取栈顶元素
        StackPop(&st);                  //将栈顶元素删除

 //将栈顶元素和*s进行匹配
 //如果出栈元素是'(',但是此时的*s不是')',说明不匹配,返回false
 //如果出栈元素是'[',但是此时的*s不是']',说明不匹配,返回false
 //如果出栈元素是'{',但是此时的*s不是'}',说明不匹配,返回false

        if(top == '(' && *s != ')' 
        || top == '[' && *s != ']' 
        || top == '{' && *s != '}')    
        {    
            //销毁栈,防止内存泄漏
            StackDestroy(&st);
            return false;
        }
    }
    s++;     //s指针继续指向下一个元素
}

哈哈哈,屏幕前的你以为这样代码就写完了吗? 肯定还没有! 因为还有一种情况我们木有考虑到~

那就是当*s已经走到'\0',但是栈不是空,说明栈里面还有左括号,不合题意, 此时StackEmpty返回false ; 如果栈为空,返回true

部分代码如下:

    bool flag = StackEmpty(&st); //用bool类型的flag变量来接受StackEmpty函数的返回值
    StackDestroy(&st);           //将栈销毁,归还给系统内存
    return flag;                 //将结果返回

好啦! 这道题被我们解决啦,整体代码如下:

typedef char ElemType;
typedef struct Stack {
	ElemType* arr;		//数组
	int top;			//栈顶
	int capacity;		//栈的容量
}Stack;

//初始化栈
void StackInit(Stack* ps);
//入栈
void StackPush(Stack* ps,ElemType data);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
ElemType StackTop(Stack* ps);
//获取栈中有效元素的个数
int StackSize(Stack* ps);
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps);
//销毁栈
void StackDestroy(Stack* ps);

//初始化栈
void StackInit(Stack* ps) {
	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//入栈
void StackPush(Stack* ps, ElemType data) {
	//扩容
	if (ps->capacity == ps->top) {
		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
		ElemType* temp =(ElemType*) realloc(ps->arr, newCapacity * sizeof(ElemType));
		if (temp == NULL) {
			perror("realloc fail!\n");
			exit(1);
		}
		ps->arr = temp;
		ps->capacity = newCapacity;
	}

	ps->arr[ps->top] = data;    //插入数据
	ps->top++;                  //栈顶向上移动一个单位
}
//出栈
void StackPop(Stack* ps) {
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
//获取栈顶元素
ElemType StackTop(Stack* ps) {
	assert(ps);
	assert(!StackEmpty(ps));
    //不改变top指针,只是获取栈顶元素
	int ret = ps->arr[ps->top - 1];
	return ret;
}
//获取栈中有效元素的个数
int StackSize(Stack* ps) {
	assert(ps);
	return ps->top; //top恰好是元素的个数
}
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps) {
	return ps->top == 0;
}
//销毁栈
void StackDestroy(Stack* ps) {
    assert(ps);
	if (ps->arr) {
		free(ps->arr);
		ps->arr = NULL;
	}
	ps->capacity = 0;
	ps->top = 0;
}

bool isValid(char* s) {
    Stack st;           //定义一个栈
    StackInit(&st);     //初始化这个栈

//当*s不等于'\0'的时候,进入while循环
while(*s){

    if(*s == '{' || *s == '[' || *s == '('){
        //将该元素放入栈内
        StackPush(&st,*s);
   }else{
        //当栈为空,且遇到右括号,栈里面没有左括号,返回false
        if(StackEmpty(&st)){
        //销毁栈,防止内存泄漏
            StackDestroy(&st);
           return false;
         }

        int top = StackTop(&st);        //获取栈顶元素
        StackPop(&st);                  //将栈顶元素删除

 //将栈顶元素和*s进行匹配
 //如果出栈元素是'(',但是此时的*s不是')',说明不匹配,返回false
 //如果出栈元素是'[',但是此时的*s不是']',说明不匹配,返回false
 //如果出栈元素是'{',但是此时的*s不是'}',说明不匹配,返回false

        if(top == '(' && *s != ')' 
        || top == '[' && *s != ']' 
        || top == '{' && *s != '}')    
        {    
            //销毁栈,防止内存泄漏
            StackDestroy(&st);
            return false;
        }
    }
    s++;     //s指针继续指向下一个元素
}

    bool flag = StackEmpty(&st); //用bool类型的flag变量来接受StackEmpty函数的返回值
    StackDestroy(&st);           //将栈销毁,归还给系统内存
    return flag;                 //将结果返回
}

片尾

今天我们学习了一道OJ题---有效的括号,里面包含了栈的一些基础知识,希望看完这篇文章能对友友们有所帮助 !  !  !

求点赞收藏加关注 !   !   !

谢谢大家 !   !   !

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【C++】力扣OJ题：找出只出现一次的数字

【C++】力扣OJ题：找出只出现一次的数字

Hello everybody!这是我第一次写关于OJ题目的博客&#xff0c;因为正好学到完了C的STL库&#xff0c;就顺手刷了一些OJ题。 我今天要介绍的题目虽然是力扣上的简单题&#xff0c;但思想很巧妙&#xff0c;我觉得有必要和大家分享一下&#xff01; 1.题目 2.代码 class Solut…
阅读更多...
【Go】原子并发操作

【Go】原子并发操作

目录 一、基本概念 支持的数据类型 主要函数 使用场景 二、基础代码实例 开协程给原子变量做加法 统计多个变量 原子标志判断 三、并发日志记录器 四、并发计数器与性能监控 五、优雅的停止并发任务 worker函数 Main函数 应用价值 Go语言中&#xff0c;原子并发操…
阅读更多...
飞机飞行数据三维可视化管控系统更智能、精准

飞机飞行数据三维可视化管控系统更智能、精准

近年来&#xff0c;随着无人化工厂和智能工厂在中国大量涌现&#xff0c;基于成熟的数字孪生理念&#xff0c;智能工厂三维可视化虚拟管控系统引领未来工业革命的先锋。数字孪生公司深圳华锐视点结合前沿的三维仿真、GIS和三维可视化技术技术&#xff0c;深度集成工厂生产、经营…
阅读更多...
鸿蒙 Failed :entry:default@CompileResource...

鸿蒙 Failed :entry:default@CompileResource...

Failed :entry:defaultCompileResource... media 文件夹下有文件夹或者图片名称包含中文字符 rawfile 文件夹下文件名称、图片名称不能包含中文字符
阅读更多...
IGBT退饱和现象解析与防范

IGBT退饱和现象解析与防范

IGBT是一种重要的功率半导体器件&#xff0c;广泛应用于电力电子领域&#xff0c;如变频器、电动机驱动、电力传输等。在这些应用中&#xff0c;IGBT的导通和关断特性至关重要&#xff0c;而退饱和是IGBT工作过程中的一个重要现象。 IGBT的退饱和定义 退饱和是指IGBT在导通状态…
阅读更多...
软件测试面试题分享（含答案+文档）

软件测试面试题分享（含答案+文档）

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 准备找工作的小伙伴们&#xff0c;今天我给大家带来了一些自动化测试面试题&#xff0c;在这个公…
阅读更多...
NLP vs. LLMs: 理解它们之间的区别

NLP vs. LLMs: 理解它们之间的区别

作者&#xff1a;Elastic Platform Team 随着人工智能持续发展并在无数行业解决问题&#xff0c;技术的一个关键部分是能够无缝地桥接人类语言和机器理解之间的差距。这就是自然语言处理&#xff08;NLP&#xff09;和大型语言模型&#xff08;LLMs&#xff09;的用武之地。它们…
阅读更多...
运用OSI模型提升排错能力

运用OSI模型提升排错能力

1. OSI模型有什么实际的应用价值&#xff1f; 2. 二层和三层网络的区别和应用&#xff1b; 3. 如何通过OSI模型提升组网排错能力&#xff1f; -- OSI - 开放式系统互联 - 一个互联标准 - 从软件和硬件 定义标准 - 不同厂商的设备 研发的技术 - 具备兼容性 -- O…
阅读更多...
Python基于flask的豆瓣电影分析可视化系统

Python基于flask的豆瓣电影分析可视化系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…
阅读更多...
初识集合框架

初识集合框架

前言~&#x1f973;&#x1f389;&#x1f389;&#x1f389; hellohello~&#xff0c;大家好&#x1f495;&#x1f495;&#xff0c;这里是E绵绵呀✋✋ &#xff0c;如果觉得这篇文章还不错的话还请点赞❤️❤️收藏&#x1f49e; &#x1f49e; 关注&#x1f4a5;&#x1f…
阅读更多...
机器视觉图像采集卡及其接口概述

机器视觉图像采集卡及其接口概述

本文主要是介绍机器视觉图像采集卡及其使用的各种接口。 首先&#xff0c;我们将概述外围计算机卡&#xff0c;然后探索图像采集卡中使用的不同类型的机器视觉接口。 我们先来说一个常见的问题&#xff1a;什么是电脑外设卡&#xff0c;如何分类&#xff1f; 用于机器视觉的…
阅读更多...
GIS 数据格式转换

GIS 数据格式转换

1、在线工具 mapshaper 2、数据上传 3、数据格式转换 导入数据可导出为多种格式&#xff1a;Shapefile、Json、GeoJson、CSV、TopJSON、KML、SVG
阅读更多...
【python】项目实战

【python】项目实战

启动一个项目对于新手都是不容易的事情 在哪 对于Windows平台&#xff0c;打开cmd 使用命令py -0p 【其中0是零】 显示已安装的 python 版本且带路径的列表 切换python3命令 在Windows下&#xff0c;可以使用cmd下使用mklink命令创建“软链接”更好一些。 例如&#xf…
阅读更多...
Three.js--》穿越虚拟门槛打造的3D登录界面

Three.js--》穿越虚拟门槛打造的3D登录界面

今天简单实现一个three.js的小Demo&#xff0c;加强自己对three知识的掌握与学习&#xff0c;只有在项目中才能灵活将所学知识运用起来&#xff0c;话不多说直接开始。 目录 项目搭建 初始化three代码 添加背景与地球 星星动画效果 星云动画效果 实现登录框效果 项目搭建…
阅读更多...
软件设计不是CRUD（18）：像搭积木一样搭建应用系统（上）——单个应用系统的搭建过程

软件设计不是CRUD（18）：像搭积木一样搭建应用系统（上）——单个应用系统的搭建过程

1、概述 之前的文章本专题花了大量文字篇幅，介绍如何基于业务抽象的设计方式完成应用系统各个功能模块的设计工作。而之所以进行这样的功能模块设计无非是希望这些功能模块在具体的项目实施过程中，能够按照当时的需求快速的、简易的、稳定的、最大可能节约开发成本的形成可用…
阅读更多...
提高大型语言模型 (LLM) 性能的四种数据清理技术

提高大型语言模型 (LLM) 性能的四种数据清理技术

原文地址&#xff1a;four-data-cleaning-techniques-to-improve-large-language-model-llm-performance 2024 年 4 月 2 日 检索增强生成&#xff08;RAG&#xff09;过程因其增强对大语言模型&#xff08;LLM&#xff09;的理解、为它们提供上下文并帮助防止幻觉的潜力而受…
阅读更多...
关于沃进科技无线模块demo软件移植问题

关于沃进科技无线模块demo软件移植问题

文章目录 一、无线模块开发测试准备二、开发板硬件三、开发板默认功能上电默认界面功能选择界面数据包发送界面数据包接收显示界面射频性能测试界面参数设置界面固件信息显示界面 四、软件开发软件SDK框图1、射频硬件驱动&#xff08;详见./radio/myRadio_gpio.c&#xff09;2、…
阅读更多...
Linux_iptables防火墙学习笔记

Linux_iptables防火墙学习笔记

文章目录 iptables 概述四表五链iptables 安装启动iptables 配置详解iptables配置文件iptables配置语法iptables常用实例查看规则修改默认规则保存和备份规则恢复备份的规则清空规则放行SSH服务在ubuntu14.04中iptables规则持久化 iptables 概述 主机型 对主机进行保护 网络型…
阅读更多...
CSS基础：margin属性4种值类型，4个写法规则详解

CSS基础：margin属性4种值类型，4个写法规则详解

你好&#xff0c;我是云桃桃。 一个希望帮助更多朋友快速入门 WEB 前端的程序媛。大专生&#xff0c;一枚程序媛&#xff0c;感谢关注。回复 “前端基础题”&#xff0c;可免费获得前端基础 100 题汇总&#xff0c;回复 “前端工具”&#xff0c;可获取 Web 开发工具合集 268篇…
阅读更多...
计算机网络入门之什么是网络

计算机网络入门之什么是网络

阅读更多...
最新文章

Copyright @ 2022~2023