题目练习之有效的括号

用户11352420

发布于 2024-11-07 21:39:53

760

发布于 2024-11-07 21:39:53

文章被收录于专栏：编程学习

在前面我们已经学习了一些基本的数据结构以及进行一些算法题练习，领会到了一些算法题巧妙的算法思路~这一篇博客依然是关于算法题的练习~继续在算法的世界里面遨游~

有效的括号

有效的括号： https://leetcode.cn/problems/valid-parentheses/description/

这里的括号需要左边的括号与右边的括号进行匹配，（与）匹配，[ 与 ]匹配，{ 与 }匹配，这个题如果我们使用常规的方法并不好解决~这里就需要用到我们的数据结构知识来解决这个问题啦~

思路

将字符串遍历，如果是当前字符是左括号就入栈，如果当前字符是右括号就将它与取到的栈顶元素进行匹配，如果不匹配就return false，然后再出栈（删除当前元素），在出栈前需要判断栈是否为空，如果为空说明栈目前没有左括号，显然这是不匹配的（左括号应该在左边，右括号在右边）return false，遍历字符串结束，这里需要判断栈是否为空，避免有左括号没有匹配的情况，为空返回true，不为空返回false。注意

可能有一些难理解，我们一步步来看~

首先将栈的一些基本实现拿过来用

//栈的基本实现
typedef char StackDatatype;
//这个题目中栈保存的数据是字符
typedef struct Stack
{
	StackDatatype* arr;
	int top;
	int capacity;
}Stack;
//初始化
void StackInit(Stack* ps)
{
	assert(ps);

	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}
//入栈
void StackPush(Stack* ps, StackDatatype x)
{
	assert(ps);
	//判断容量是否足够
	if (ps->top == ps->capacity)//空间已满
	{
		int newcapacity = (ps->capacity == 0) ? 4 : 2 * (ps->capacity);
		StackDatatype* temp = realloc(ps->arr, sizeof(StackDatatype) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		else
		{
			ps->arr = temp;
			ps->capacity = newcapacity;
		}
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

//判断栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
	//栈没有元素
}
//取栈顶元素
StackDatatype StackTop(Stack* ps)
{
	assert(ps);
	//栈不能为空
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}


//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

//获取栈有效个数
int StackCount(Stack* ps)
{
	assert(ps);
	return ps->top;
}

//栈销毁
void StackDestory(Stack* ps)
{
	assert(ps);
	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

实现函数代码及详细解释：

bool isValid(char* s)
{
    assert(s);//字符串地址有效
    Stack st;
    StackInit(&st);//初始化栈
    char* pcur = s;
    //遍历字符串左括号入栈
    while ((*pcur) != '\0')
    {
        if ((*pcur) == '(' || (*pcur) == '[' || (*pcur) == '{')
        {
            //入栈
            StackPush(&st, (*pcur));
        }
        //！！！每一次返回true或者false前要进行栈销毁
        else//遇到右括号取栈顶元素比较是否匹配
        {
            if (StackEmpty(&st))
                //栈为空,目前只有右括号，前面没有左括号匹配
            {
                StackDestory(&st);
                return false;
            }
            //取栈顶元素比较
            StackDatatype re = StackTop(&st);
            //当前字符与栈顶元素不匹配
            if ((re == '(' && *pcur != ')') ||
                (re == '[' && *pcur != ']') ||
                (re == '{' && *pcur != '}'))
            {
                StackDestory(&st);
                return false;
            }
            //满足当前数据出栈
            StackPop(&st);
        }
        pcur++;//继续往后面遍历
    }
    //判断栈是否为空
    //栈不为空，还有左边括号没有匹配
    /*if(StackEmpty(&st))
    {
        StackDestory(&st);
        return true;
    }
    else
    {
        StackDestory(&st);
        return false;
    }*/
    //优化
    bool ret = StackEmpty(&st) ? true : false;
    //使用bool类型保存返回值
    StackDestory(&st);
    return ret;
}

结合着代码来看，是不是更加清晰呢？我们也就完成了这一段代码，提交一下看能否通过？