您现在的位置是:首页 >技术教程 >【力扣-20】有效的括号网站首页技术教程

【力扣-20】有效的括号

D. Star. 2023-07-09 16:00:03
简介【力扣-20】有效的括号

🖊作者 : D. Star.
📘专栏 : 数据结构
😆今日分享 : 夏虫不可以语冰 : 出自「庄子·秋水」。原句是“井蛙不可以语于海者,拘于虚也;夏虫不可以语于冰者,笃于时也;曲士不可以语于道者,束于教也”。而这句话的意思就是,一种虫子如果它生命周期只有夏天这几个月,你跟它说冰是什么东西,它是不会知道的,它想象不出来那个东西,因为它的生命周期从来不经过冬天。
这句话常常用来比喻时间局限人的见识,也比喻人的见识短浅,不懂大道理。
在这里插入图片描述

请添加图片描述

🌻题目链接:

做题链接

🌻题目详情:

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

有效字符串需满足:

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

示例:在这里插入图片描述

🌻解题思路:

解题思路:
 循环遍历String中的字符,逐个取到每个括号,如果该括号是:
    1. 左括号,直接入栈
    2. 右括号,与栈顶的左括号进行匹配,如果不匹配直接返回false
       否则继续循环
 循环结束后,如果栈空则匹配,否则左括号比右括号多肯定不匹配

🔎代码详情:

#define DataType char
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef struct Stack
{
	DataType* a;
	int top;
	int capacity;
}ST;
//初始化
void stackInit(ST* st)
{
	assert(st);//断言st是否是空指针(因为assert不能为空)

	st->a = (DataType*)malloc(sizeof(DataType));//1个空间
	if (st->a == NULL)
	{
		perror("malloc fail:");
		exit(-1);
	}
	st->capacity = 1;
	st->top = -1;
}

//销毁
void stackDestory(ST* st)
{
	assert(st);//断言st是否是空指针(因为assert不能为空)

	free(st->a);//注意:这里free的是数组的空间,不是结构体
	st->a = NULL;
	st->capacity = 0;
	st->top = -1;
}

//入栈
void stackPush(ST* st, DataType x)
{
	assert(st);//断言st是否是空指针(因为assert不能为空)

	//不为空时,入栈
	// 判断数组是否满
	if (st->top + 1 == st->capacity)
	/*if(st->capacity == st->top )*/
	{
		DataType* tmp = (DataType*)realloc(st->a, 2 * sizeof(DataType) * st->capacity );
		//开辟空间失败时,返回
		if (tmp == NULL)
		{
			perror("realloc fail : ");
			exit(-1);
		}
		//成功时,将开辟空间的地址给到st->a
		st->a = tmp;
		st->capacity *= 2;
	}
	//尾插
	st->top++;
	st->a[st->top] = x;
}

//出栈
void stackPop(ST* st)
{
	assert(st);
	assert(st->top > -1);

	//出栈
	st->top--;
}

//判断栈是否为空
bool stackEmpty(ST* st)
{
	assert(st);
	// //法一:
	// if (st->top > -1)
	// {
	// 	return false;
	// }
	// else return true;
	
	//法二:
	return !(st->top > -1);
}

//获取栈顶元素
DataType stackTop(ST* st)
{
	assert(st);
	assert(!stackEmpty(st));
 
	return st->a[st->top];
}


bool isValid(char * s){
    ST st;
    stackInit(&st);//初始化先
    while(*s)
    {
        if((*s == '{') || (*s == '(') || (*s == '['))
         {
        //如果是左括号,则入栈
        stackPush(&st,*s);
        s++;
        }
        else
        {
            //如果栈为空,即没有左括号与右括号匹配,则false;
            
            if(stackEmpty(&st))
                return false;
          //如果不是左括号,则提取栈顶元素与当前的元素进行比较是否配对;
           if((stackTop(&st) == '(' && *s == ')') || 
           (stackTop(&st) == '[' && *s == ']') || 
           (stackTop(&st) == '{' && *s == '}'))
             {
            //如果相等,则进行下一个比较;
                 s++;
                 stackPop(&st);
             }
             else
             {
                //如果不相等,则false;
                 return false;
             }
        }
    }
    //如果右括号匹配完,左括号还有的话(不为空),也是false;
    bool ret = stackEmpty(&st);
    stackDestory(&st);
    return ret;
}

🌻总结:

  1. 调用的方法,必须放在该函数前面
  2. 思路要清晰,知道自己需要哪些变量

感谢家人的阅读,若有不准确的地方 欢迎在评论区指正!

家人们,点个请添加图片描述再走呗~

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