C语言每日一题（35）有效的括号

对编程一片赤诚的小吴

发布于 2024-01-23 15:10:32

720

发布于 2024-01-23 15:10:32

文章被收录于专栏：热爱编程的证据热爱编程的证据

力扣网 20 有效的括号

题目描述

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

思路分析

如果这里再用所谓的遍历字符串寻找进行匹配的话，时间复杂度高且不说，还麻烦，但如果我们学习栈了以后，这道题会变得异常轻松。

我们将所有的左括号入栈，在字符串里找右括号，同时出栈左括号进行匹配，如果匹配成功就返回true，否则返回false。

注意的问题：

这里除了括号类型的匹配问题，同时还有数量问题，会存在左括号多于右括号或者反过来的情况，这里如果数量不匹配的话也返回false。

判断数量的问题，再寻找右括号时，先判断栈是否为空，这是判断右括号多余左括号的情况，

在遍历一遍字符串后，如果栈里面还有括号，说明左括号多于右括号，也返回false。

完整代码

力扣环境下是不提供栈的，这里我们需要自己定义。

栈定义和常用接口

头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int _top;
	int _capacity;
}Stack;

// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);

接口实现文件

#include"Stack.h"

// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}

// 入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//检查是否栈满
	if (ps->_top == ps->_capacity)
	{
		int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		Stack* ptr = realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (ptr == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = ptr;
		ps->_capacity = newcapacity;
		
	}
	//入栈
	ps->a[ps->_top] = data;
	ps->_top++;
}

// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	ps->_top--;
}

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

	return ps->a[ps->_top-1];
}

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->_top == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->_capacity = 0;
	ps->_top = 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 top = StackTop(&st);//出栈栈顶括号
            StackPop(&st);
            if (*s == ']' && top != '[' ||//两者进行匹配，如果存在不等情况，返回false
                *s == '}' && top != '{' ||
                *s == ')' && top != '(')
            {
                StackDestroy(&st);
                return false;
            }

        }
        ++s;
    }
    bool ret = StackEmpty(&st);//最后再判断栈是否为空（左括号多余右括号情况），布尔值，如果栈为空返回真，否则返回假
    StackDestroy(&st);
    return ret;
}