当前位置：首页 > article >正文

【力扣刷题实战】有效的括号

article 2024/10/26 0:24:38

大家好，我是小卡皮巴拉

文章目录

力扣题目：有效的括号

题目描述

示例 1：

示例 2：

示例 3：

示例 4：

解题思路

问题理解

算法选择

具体思路

解题要点

完整代码（C语言）

兄弟们共勉！！！

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

力扣题目：有效的括号

原题链接：有效的括号

题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

解题思路

问题理解

题目要求我们判断一个仅包含括号（'('，')'，'{'，'}'，'['，']'）的字符串是否有效。有效字符串需满足以下条件：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。

算法选择

我们可以使用栈（Stack）这一数据结构来解决这个问题。栈的特点是后进先出（LIFO），非常适合处理这种需要匹配和回溯的问题。

具体思路

初始化栈：首先，我们需要一个栈来存储左括号。在C语言中，我们可以定义一个栈的数据结构ST，并初始化它。

遍历字符串：使用指针pi遍历输入的字符串s。

处理左括号：如果当前字符是左括号（'('、'{'、'['），则将其压入栈中。

处理右括号：

首先检查栈是否为空。如果为空，说明没有对应的左括号来匹配当前的右括号，因此字符串无效。

如果栈不为空，取出栈顶元素（即最近入栈的左括号），并检查它是否与当前的右括号匹配。

如果不匹配，或者栈顶元素不是对应的左括号，则字符串无效。

如果匹配，则弹出栈顶元素（即移除已匹配的左括号）。

遍历结束后检查：遍历完整个字符串后，检查栈是否为空。如果为空，说明所有左括号都得到了正确匹配和闭合，字符串有效；否则，字符串无效。

销毁栈：在返回结果之前，销毁栈以释放分配的内存。

解题要点

栈的使用：用于存储左括号，并在遇到右括号时弹出栈顶元素进行匹配。

括号匹配：使用哈希表或数组来快速判断右括号是否与栈顶的左括号匹配。

遍历结束后的检查：遍历结束后，栈应为空，否则说明有未匹配的左括号。

完整代码（C语言）

typedef char STDataType;
//定义栈的数据结构
typedef struct Stack
{
	STDataType* arr;
	int top;//指向栈顶位置
	int capacity;
}ST;
//初始化
void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

//销毁
void STDestroy(ST* ps)
{
	if (ps->arr != NULL)
		free(ps->arr);

	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

//入栈——栈顶
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		//空间满了，增容
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!\n");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

//栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

//出栈——栈顶
void StackPop(ST* ps)
{
	assert(!StackEmpty(ps));
    ps->arr[(ps->top)--];
}

//取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(!StackEmpty(ps));
	return ps->arr[ps->top - 1];
}
bool isValid(char* s) {
    //借助数据结构——栈，遇到左括号就入栈，遇到右括号就取栈顶元素检查是否是与之对应的右括号
    ST st;
    STInit(&st);
    char* pi = s;
    while(*pi != '\0')
    {
        if(*pi == '(' || *pi == '{' || *pi == '[')
        {
            //入栈
            StackPush(&st,*pi);
        }else
        {
            //取栈顶，判断
            if(StackEmpty(&st))
               return false;
            char top = StackTop(&st);
            if((top =='('&& *pi != ')')
            ||(top == '['&& *pi !=']')
            ||(top == '{'&& *pi != '}'))
               return false;
            StackPop(&st);
        }
        pi++;
    }
    bool ret = StackEmpty(&st) ? true:false;
    STDestroy(&st);
    return ret;
}