【数据结构OJ题】有效的括号

这篇具有很好参考价值的文章主要介绍了【数据结构OJ题】有效的括号。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

原题链接:https://leetcode.cn/problems/valid-parentheses/

目录

1. 题目描述

2. 思路分析

3. 代码实现


1. 题目描述

【数据结构OJ题】有效的括号,数据结构,数据结构,栈,c语言,动态顺序表,字符串,leetcode

 文章来源地址https://www.toymoban.com/news/detail-658003.html

2. 思路分析

这道题目主要考查了的特性:

题目的意思主要是要做到3点匹配:类型、顺序、数量

题目给的例子是比较简单的情况,可能还有如下较为复杂的情况:

【数据结构OJ题】有效的括号,数据结构,数据结构,栈,c语言,动态顺序表,字符串,leetcode

循环遍历字符串s中的字符,逐个取到每个括号,如果该括号是:

1. 左括号,入栈
2. 右括号,出栈顶括号,进行匹配。

 如果不匹配,直接返回false。否则继续循环。

 循环结束后如果栈空则匹配否则左括号比右括号多肯定不匹配

3. 代码实现

typedef char STDataType;
#define INIT_CAPACITY 4
typedef struct Stack
{
	STDataType* a;
	int top;  //栈顶
	int capacity;  //容量
}ST;

//初始化栈
void STInit(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空
bool STEmpty(ST* ps);
//销毁栈
void STDestroy(ST* ps);

void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);
	//空
	assert(ps->a > 0);
	--ps->top;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	//空
	assert(ps->a > 0);
	return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

void STDestroy(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

bool isValid(char * s){
    ST st;
    STInit(&st);
    char topVal;
    while(*s)
    {
        if(*s=='('||*s=='{'||*s=='[')
        {
            STPush(&st,*s);
        }
        else
        {
            if(STEmpty(&st))
            {
                STDestroy(&st);
                return false;
            }
						topVal=STTop(&st);
            if(*s==')'&&topVal!='('
                ||*s=='}'&&topVal!='{'
                ||*s==']'&&topVal!='[')
            {
                STDestroy(&st);
                return false;
            }
			else
			{
				STPop(&st);
			}
        }
        ++s;
    }
    bool ret=STEmpty(&st);
    STDestroy(&st);
    return ret;
}

【数据结构OJ题】有效的括号,数据结构,数据结构,栈,c语言,动态顺序表,字符串,leetcode

 

到了这里,关于【数据结构OJ题】有效的括号的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言数据结构-----顺序表(多功能动态顺序表的代码实现)

    本篇讲述了顺序表的相关知识,以及动态顺序表的代码实现。 顺序表和链表一般情况下都会叫他们线性表。 线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性

    2024年02月07日
    浏览(48)
  • 追梦之旅【数据结构篇】——详解C语言动态实现顺序表

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2024年01月24日
    浏览(42)
  • 『初阶数据结构 • C语言』⑧ - 动态顺序表详解(附完整源码)

    本章内容 写在前面 1.静态与动态是指什么? 2.动态顺序表结构的定义 3.动态顺序表的函数接口实现 4.动态顺序表的问题及思考 5.关于顺序表的OJ题 6.OJ答案及解析 1.移除元素 2.删除有序数组中的重复项 ​3.合并两个有序数组 7.动态顺序表完整源码 1.SeqList.h 2.SeqList.c     上一章

    2024年02月16日
    浏览(45)
  • [C语言][数据结构][动态内存空间的开辟]顺序表的实现!

    目录 零.必备知识 a.顺序表的底层是数组. b.数组在内存中是连续存放的. c.动态内存空间的开辟(malloc,calloc,realloc). 一.顺序表的定义与实现          1.1 顺序表的定义          1.2 顺序表的初始化          1.3 顺序表的销毁          1.4 顺序表容量的检查与调整

    2024年04月09日
    浏览(88)
  • 【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号

    🌱 栈 是一种特殊的线性表, 只能在一端进行操作 🌱 往栈中 添加 元素的操作,一般叫做 push ( 入栈 ) 🌱 从栈中 移除 元素的操作,一般叫做 pop ,出栈(只能移除栈顶元素),也叫做: 弹出栈顶元素 🌱 后进先出 的原则, L ast I n F irst O ut, LIFO 注意:这里的 栈 与内

    2024年02月13日
    浏览(39)
  • 顺序表链表OJ题(2)->【数据结构】

    W...Y的主页 😊 代码仓库分享 💕 前言: 单链表的结构常常不完美,没有双向链表那么”优秀“,所以繁衍出很多OJ练习题。今天我们继续来look look数据结构习题。 下面就是OJ时间!!! 【链表中倒数第K个节点】——牛客网 OJ链接 描述 输入一个链表,输出该链表中倒数第

    2024年02月10日
    浏览(41)
  • 顺序表链表OJ题(3)——【数据结构】

    W...Y的主页 😊 代码仓库分享 💕 前言:  今天是链表顺序表OJ练习题最后一次分享,每一次的分享题目的难度也再有所提高,但是我相信大家都是非常机智的,希望看到博主文章能学到东西的可以一键三连关注一下博主。 话不多说,我们来看今天的OJ习题.。 【leetcode 142.环

    2024年02月10日
    浏览(45)
  • 数据结构与算法之字符串: Leetcode 20. 有效的括号 (Typescript版)

    有效的括号 https://leetcode.cn/problems/valid-parentheses/ 描述 给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相

    2024年02月01日
    浏览(54)
  • 数据结构(C语言实现)——栈和队列的介绍及基本操作的实现(动态顺序栈+链队)

    今天我们来学习另外两个线性结构——栈和队列,栈和队列是操作受限的线性表,因此,可称为限定性的数据结构。 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守

    2023年04月19日
    浏览(44)
  • 【数据结构】——线性表(顺序表加链表),万字解读(加链表oj详解)

    前言 由于之前存在过对两者的区别考虑,所以把他们放在一起来说,更加容易区别和理解 对于有关线性表的概念这里就不展示了,这里主要是介绍线性表里面的这两个结构的知识点 一.顺序表 1.顺序表介绍 顺序表的存储结构和逻辑结构都是相邻的, 这里如果我们把a1的地址

    2024年03月22日
    浏览(89)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包