前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode刷题(6)【栈】有效的括号(C语言)

LeetCode刷题(6)【栈】有效的括号(C语言)

作者头像
半生瓜的blog
发布2023-05-12 21:21:45
3690
发布2023-05-12 21:21:45
举报
文章被收录于专栏:半生瓜のblog半生瓜のblog

有效的括号

20. 有效的括号 - 力扣(LeetCode) (leetcode-cn.com) 思路:是左括号,就入栈,是右括号,就与栈顶的左括号判断是否匹配,如果匹配,继续,不匹配就终止。 从第79行开始,前面都是实现栈以及其功能接口。

代码语言:javascript
复制
typedef char StackDataType;
typedef struct Stack
{
	StackDataType* arry;
	int top;//指向栈顶
	int capacity;//栈的容量——能放几个数据
}Stack;
//初始化
void StackInit(Stack* ps)
{
	assert(ps);
	ps->arry = (StackDataType*)malloc(sizeof(StackDataType)*4);
	if (ps->arry == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}
//销毁
void StackDestory(Stack* ps)
{
	assert(ps);
	free(ps->arry);
	ps->arry = NULL;
	ps->top = ps->capacity =0 ;
}
//入栈
void StackPush(Stack* ps, StackDataType x)
{
	assert(ps);
	//满了
	if (ps->top == ps->capacity)
	{
		StackDataType* tmp = (StackDataType*)realloc(ps->arry, ps->capacity * 2 * sizeof(StackDataType));
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		else
		{
			ps->arry = tmp;
			ps->capacity *= 2;
		}
	}
	ps->arry[ps->top] = x;
	ps->top++;
} 

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//如果栈空了调用top,直接终止程序报错
	assert(ps->top > 0);
	ps->top--;
}
//返回栈顶元素
StackDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->arry[ps->top - 1];
}
//返回栈中元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
//是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;//真为空,假为非空。
}
///
bool isValid(char * s){
    Stack  st;
    StackInit(&st);
    while(*s != '\0')
    {
        switch(*s)
        {
            case '{':
            case '[':
            case '(':
            {
                StackPush(&st,*s);
                s++;
                break;
            }
            case '}':
            case ']':
            case ')':
            {
                if(StackEmpty(&st))
                {
                    StackDestory(&st);
                    return false;
                }

                char top = StackTop(&st);
                StackPop(&st);

                //不匹配的三种情况  
                if((*s == '}'&& top != '{')
                || (*s == ']'&& top != '[')
                || (*s == ')'&& top != '('))
                {
                  //不匹配返回fasle,有可能栈里面还有元素,销毁防止内存泄漏
                    StackDestory(&st);
                    return false;
                }
                else
                {
                    //匹配就继续匹配
                    s++;   
                }
                break;
            }
            default:
                break;
        }
    }
    bool ret = StackEmpty(&st);//匹配完成了,栈应该是空的。
    StackDestory(&st);
    return ret;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2021-06-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档