• 数据结构每日亿题(五)

    有效的括号

    原题传送门：力扣

    题目：
    在这里插入图片描述这题的大概意思是给你一堆括号让你判断它左右两种括号是否匹配，但是像([)]这样子的不算，只有(({{}})){}这样子才算合法。

    1.每个左括号都要有一个对应的右括号。
    一个括号的另一半不能在另一对括号里面。

    大约就这意思，我觉得我应该说明白了

    但是题目是弄懂了，但是要如何去做呢？一个一个去遍历吗？我们可以这样想，从头开始把左括号集中在一起，走着走着如果突然碰到一个右括号，是不是这个右括号只有与刚才那么多的左括号中最后一个括号相匹配时，才算成功？这样思路就来了：

    我们定义一个栈，将这些括号从左到右依次遍历如果是左括号就把它放到栈里。
    但是前提我们要先定义一个栈，并且写上一些关于栈实现的函数，这些函数我在数据结构：栈中已经讲过了，现在我直接拿过来，并把一些这题用不到的函数去掉。

    typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int capacity; //栈空间大小
	int top; // 栈顶
}Stack;

// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);

	//刚开始为栈提前开辟4个元素的空间
	ps->a = (STDataType*)malloc(4 * sizeof(STDataType));
	if (ps->a == NULL)
	{
		perror("StackInit");
		exit(-1);
	}

	ps->capacity = 4;
	ps->top = 0; //这里top指向栈顶元素的下一个位置
}

//入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//在栈尾添加一个元素

	//首先判断需不需要扩容
	if (ps->capacity == ps->top)
		//相等说明此时元素个数已经和总容量相等了，如果在添加元素需要扩容
	{
		//扩容为原来的两倍
		STDataType* cap = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (cap == NULL)
		{
			perror("StackPush");
			exit(-1);
		}

		ps->a = cap;
		ps->capacity *= 2;
	}

	ps->a[ps->top] = data;
	ps->top++;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//如果栈里面没有元素了，就不能进行出栈的操作
	assert(ps->top);

	ps->top--;
}

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);

	assert(ps->top != 0);
	return ps->a[ps->top - 1];
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

//销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84

    如果在力扣上写这题时，这些把这些函数拷上去就行，拿着就能用。

    现在我们先从头开始遍历，把左括号都通过压栈压到栈里面去：

    	//定义一个栈的结构体
    Stack st;
    //初始化这个结构体
    StackInit(&st);
    //从头开始遍历，直到*s指向字符串的尾部\0
    while(*s)
    {
        if(*s == '(' || *s == '[' || *s == '{')
        {
        	//压栈的函数
            StackPush(&st,*s);
            //压完之后指针向后走一步
            s++;
        }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    如果此时突然碰到一个右括号呢？此时把剩下的函数写出来：(注意上下这两部分代码应该是连在一起的。)

           else
        {
            char tmp = StackTop(&st);
            if(*s == ')' && tmp != '('
            || *s == ']' && tmp != '['
            || *s == '}' && tmp != '{')
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
                StackPop(&st);
                s++;
            }
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    如果遇到了一个右括号，我们把此时的栈顶元素取出来，然后看看栈顶元素和这个右括号的关系。这里我们这样规定：
    如果这个右括号和栈顶元素的括号不匹配，说明这个字符串已经没有效了。

    如果两个括号匹配，就跳到else的语句中，我们把这个栈顶元素弹出去，并且指向字符串的指针向后走一步。这样的目的我是想，只要找到一对匹配的括号就把这一对删掉，这样下个右括号匹配的就是新的栈顶元素了。

    像这样指针从头开始一直往后走，遍历完之后也就是while循环结束了，就可以说明这个字符串是有效的了，因为只要有一个无效，就已经在循环时返回完了，不可能活到循环结束。

    所以代码可以这样写：

    bool isValid(char * s){
    Stack st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '(' || *s == '[' || *s == '{')
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            //将此时的元素与栈顶元素比较
            char tmp = StackTop(&st);
            if(*s == ')' && tmp != '('
            || *s == ']' && tmp != '['
            || *s == '}' && tmp != '{')
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
                StackPop(&st);
                s++;
            }
        }
    }
    StackDestroy(&st);
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    但是这样就完了吗/NO!NO!NO!.还要考虑一些特殊情况：

    1. 字符串只有一个左括号：
      如果只有一个左括号，在进入循环时，把这个元素压到栈里面，指针++，此时发现直接跳出循环了，跳出去之后发现直接返回了true，这肯定是不对的。所以我们在末尾还要加一个判断：如果此时栈不为空，说明还有括号没有匹配，这样只能返回false，所以在销毁栈之前加一个这个代码：
    //StackEmpty(&st)返回false说明此时栈不为空
    if(StackEmpty(&st) == false)
    {
        StackDestroy(&st);
        return false;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    1. 只有一个右括号：
      稍微想一下就可以知道如果第一个字符是右括号或者只有一个右括号的时候，这个字符串必然不是有效的。因为此时不可能有左括号和他匹对。所以我们在加一段代码：
    if(StackEmpty(&st) == true)
{
	StackDestroy(&st);
	return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    我们把这段代码加在第一个else后面：

        while(*s)
    {
        if(*s == '(' || *s == '[' || *s == '{')
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            if(StackEmpty(&st) == true)
            {
                StackDestroy(&st);
                return false;
            }
            //将此时的元素与栈顶元素比较
            char tmp = StackTop(&st);
            if(*s == ')' && tmp != '('
            || *s == ']' && tmp != '['
            || *s == '}' && tmp != '{')
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
                StackPop(&st);
                s++;
            }
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    为什么加在这里的，因为在判断第一个字符是左括号还是右括号时，如果是右括号代码肯定不会执行if里面的代码，而是去执行else里面的代码，因为跳过了if语句，所以栈肯定是空的，此时说明这个字符串的第一个字符是右括号此时直接返回false就行。

    这样我们的代码就写完了。

    完整代码

    typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int capacity; //栈空间大小
	int top; // 栈顶
}Stack;

// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);

	//刚开始为栈提前开辟4个元素的空间
	ps->a = (STDataType*)malloc(4 * sizeof(STDataType));
	if (ps->a == NULL)
	{
		perror("StackInit");
		exit(-1);
	}

	ps->capacity = 4;
	ps->top = 0; //这里top指向栈顶元素的下一个位置
}

//入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//在栈尾添加一个元素

	//首先判断需不需要扩容
	if (ps->capacity == ps->top)
		//相等说明此时元素个数已经和总容量相等了，如果在添加元素需要扩容
	{
		//扩容为原来的两倍
		STDataType* cap = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (cap == NULL)
		{
			perror("StackPush");
			exit(-1);
		}

		ps->a = cap;
		ps->capacity *= 2;
	}

	ps->a[ps->top] = data;
	ps->top++;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//如果栈里面没有元素了，就不能进行出栈的操作
	assert(ps->top);

	ps->top--;
}

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);

	assert(ps->top != 0);
	return ps->a[ps->top - 1];
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

//销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

bool isValid(char * s){
    Stack st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '(' || *s == '[' || *s == '{')
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            if(StackEmpty(&st) == true)
            {
                StackDestroy(&st);
                return false;
            }
            //将此时的元素与栈顶元素比较
            char tmp = StackTop(&st);
            if(*s == ')' && tmp != '('
            || *s == ']' && tmp != '['
            || *s == '}' && tmp != '{')
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
                StackPop(&st);
                s++;
            }
        }
    }
    if(StackEmpty(&st) == false)
    {
        StackDestroy(&st);
        return false;
    }
    StackDestroy(&st);
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
  • 相关阅读:
    【论文阅读】基于强化学习框架的A/B测试中的动态因果效应评估
    Three.js中实现对InstanceMesh的碰撞检测
    《数据结构：c语言版》（严蔚敏）知识点整合
    （一）基于centos7.9安装最新版本kubernetes(1.25.2)
    北斗导航 | GNSS观测模型（公式推导）
    数字时代，VR虚拟展会打造全渠道同步营销新模式
    vue+StringBoot map传参
    PostgreSQL教程（三十一）：服务器管理（十三）之监控数据库活动
    FISCO BCOS 3.0【01】搭建第一个区块链网络
    lightdb 支持兼容Oracle的to_clob函数
  • 原文地址：https://blog.csdn.net/weixin_57418095/article/details/127812772