您现在的位置是:首页 >其他 >栈和队列OJ题:LeetCode--20.有效的括号网站首页其他

栈和队列OJ题:LeetCode--20.有效的括号

stackY、 2024-06-17 10:47:11
简介栈和队列OJ题:LeetCode--20.有效的括号

朋友们、伙计们,我们又见面了,本期来给大家解读一下数据结构方面有关链表的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!

数 据 结 构 专 栏:数据结构

个    人   主    页 :stackY、

LeetCode 专  栏 :LeetCode刷题训练营

LeetCode--20.有效的括号:https://leetcode.cn/problems/valid-parentheses/

1.题目介绍

给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。

2.实例演示

3.解题思路

本道题最简单有效的方法就是使用栈来进行解题,如果你不了解栈可以看看我的这篇博客:数据结构:栈和队列

因为栈是先入后出,因此这样就保证了括号匹配时都是与最近的括号进行匹配,我们可以先创建一个栈,然后遍历这个字符数组,然后将右括号入栈,然后使用左括号来进行一一的匹配,匹配成功之后再进行出栈,如果每一个右括号都有与之匹配的左括号,那么就返回true,如果匹配不成功就返回false,那么在这里要注意几个小小的细节:

1.如果没有右括号入栈,还使用左括号匹配,这时就可以不用匹配了,可以直接返回false。

2.假如s这个字符数组中只有一个右括号,那么还需要在最后检测一下栈,如果栈不为空,那么就证明还有右括号没有匹配成功,因为如果匹配成功就会出栈,所以我们可以设定一个bool的检测值,将这个检测值作为最后的返回值。

正常情况:

 特殊情况1:

 特殊情况2:

 

代码演示:

//动态栈
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;        //栈顶
	int capacity;  //栈的容量
}Stack;


//对栈的初始化
void StackInit(Stack* pst);

//入栈
void StackPush(Stack* pst, STDataType x);

//出栈
void StackPop(Stack* pst);

//获取栈顶元素
STDataType StackTop(Stack* pst);

//获取栈中的有效元素的个数
int StackSize(Stack* pst);

//检测栈是否为空
bool StackEmpty(Stack* pst);

//销毁栈
void StackDestroy(Stack* pst);

//对栈的初始化
void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = NULL;
	//top为-1时,插入一个数据之后top指向的是刚刚插入数据的位置
	//pst->top = -1     
	//top为0时,插入一个数据之后top指向的是刚刚插入数据后面的位置
	pst->top = 0;
	pst->capacity = 0;
}

//入栈
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	//检测容量
	if (pst->top == pst->capacity)
	{
		int NewCapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		//当pst->a为NULL时执行的功能是和malloc一样
		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 StackPop(Stack* pst)
{
	assert(pst);
	//判断栈是否为空
	assert(!StackEmpty(pst));
	//出栈
	pst->top--;
}

//获取栈顶元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	//top指向的是栈顶的下一个位置的元素
	return pst->a[pst->top - 1];
}

//获取栈中的有效元素的个数
int StackSize(Stack* pst)
{
	assert(pst);

	return pst->top;
}

//检测栈是否为空
bool StackEmpty(Stack* pst)
{
	assert(pst);
	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return pst->top == 0;
}

//销毁栈
void StackDestroy(Stack* pst)
{
	assert(pst);

	//释放
	free(pst->a);
	pst->a = NULL;
	//重置为0
	pst->top = pst->capacity = 0;
}

bool isValid(char* s) {

	Stack st;
	StackInit(&st);

	while (*s)
	{
		//右括号入栈
		if (*s == '('
			|| *s == '{'
			|| *s == '[')
		{
			StackPush(&st, *s);
		}
		//左括号进行匹配
		else
		{
			//如果没有右括号插入可以直接返回假
			if (StackEmpty(&st))
			{
				//返回前先要销毁
				StackDestroy(&st);
				return false;
			}
			//保存栈顶的数据
			char tmp = StackTop(&st);
			//再出栈
			StackPop(&st);
			//进行匹配
			//匹配不成功的话就返回假
			//匹配成功的话继续匹配后面的
			if ((*s == '}' && tmp != '{')
				|| *s == ')' && tmp != '('
				|| *s == ']' && tmp != '[')
			{
				StackDestroy(&st);
				return false;
			}
		}
		//迭代
		s++;
	}
	//检测栈中是否还有未匹配成功的右括号
	bool ret = StackEmpty(&st);
	StackDestroy(&st);
	return ret;
}

 今天的博客就分享到这里,喜欢的老铁留下你的三连,感谢感谢!我们下期再见!!

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。