力扣---LeetCode20. 有效的括号(栈)网站首页 其他

力扣---LeetCode20. 有效的括号(栈)

小沈熬夜秃头中୧⍤⃝❅ 2024-06-17 10:48:26

简介力扣---LeetCode20. 有效的括号(栈)

文章目录

前言
?一、20. 有效的括号
?二、链接
?三、方法：栈实现
- ?3.1思路：
- ?3.2代码：
?四、补充：
?总结

前言

?个人主页：@小沈熬夜秃头中୧⍤⃝❅
?小编介绍：欢迎来到我的乱七八糟小星球?
?专栏：数据结构
?本章内容：[数据结构]—链表之带头双向循环链表
送给各位?：不能因为没有掌声就丢掉自信大起大落谁都有拍拍灰尘继续走
欢迎评论? +点赞? +收藏? +关注?哦~

?一、20. 有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：

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

?二、链接

20. 有效的括号

?三、方法：栈实现

?3.1思路：

用栈来实现，如果是左括号(" [ " " { " " ( “)就入栈，如果是右括号(” ] " " } " " ) ")就出栈，然后取出栈中的top和右括号比较，如果匹配的上就是有效括号(用C语言实现是需要创建栈的)

不懂得宝贝可以看【数据结构】— 几分钟走进栈和队列(详解-上)

?3.2代码：

typedef char STDataType;
typedef struct Strack
{
	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->top = 0;
	pst->capacity = 0;
}
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity =pst->top = 0;
}
void STPush(ST* pst, STDataType x)
{
	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(!STEmpty(pst));
	pst->top--;
}
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top-1 ];
}
bool STEmpty(ST* pst)
{
	assert(pst);
	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))
            //当为右括号没有左括号时，我们直接返回false"]"不然下面要取栈顶中的值，但是没有左括号，所以栈中为空，就会出现越界问题所以要判空一下判断栈中是否有左括号
            {
                STDestroy(&st);
                return false;
            }
            char top=STTop(&st);//取出栈顶元素
            STPop(&st);//然后将(栈顶元素)出栈
            if(top=='('&&*s!=')'||top=='['&&*s!=']'||top=='{'&&*s!='}')
            //两者不匹配时，就返回false
            {
                STDestroy(&st);
                return false;
            }
        }
        //不然就s++比较下一组
        s++;
    }
    bool ret= STEmpty(&st);//如果出现"[([ ])"这样一组匹配完栈中就会剩余”[“,所以还要对栈判空一下，如果有值bool就返回false,为空bool就返回ture
    //bool---波尔类型
    STDestroy(&st);
    return ret;
}