目录

题目链接

题目描述

思路

 代码

作者新建立的社区：非科班转码社区-CSDN社区云

期待hxd的支持哈  

题目链接

20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com)

题目描述

思路

用栈来解决这个问题。当为左括号时，入栈，为右括号时出栈，同时注意括号的个数是否匹配，如左括号多余右括号，或者右括号多余左括号的情况。（注意因为是用c语言来实现，所以我们还要单独来实现一个栈）

 代码

#include 
#include 
#include 
#include 

//struct Stack
//{
//	int a[N];
//	int top; // 栈顶的位置
//};

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶的位置
	int capacity;	// 容量
}ST;

void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
STDataType StackTop(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = 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 : ps->capacity * 2;
		ps->a = (STDataType*)realloc(ps->a, newCapacity* sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc failn");
			exit(-1);
		}

		ps->capacity = newCapacity;
	}

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

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}

bool StackEmpty(ST* ps)
{
	assert(ps);

	
	return ps->top == 0;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

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


int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if((*s=='(')||(*s=='[')||(*s=='{'))
        {
            //左括号就入栈   右括号就出栈
            StackPush(&st,*s);
            s++;
        }
        else
        {
            //如果需要出栈 但是已经没有可出的了，说明不匹配直接return
            //如： ()) 
            if(StackEmpty(&st))
            return false;

            //取栈顶
            char top=StackTop(&st);
            StackPop(&st);
            //因为继续的条件有很多，所以我们判断return的条件
            //这里很值得注意
            if((*s==')' && top!='(')
            ||(*s==']' && top!='[')
            ||(*s=='}' && top!='{'))
            {
                StackDestory(&st);
                return false;
            }
            s++;
        }
    }

    //如果栈此时不等于空，就说明左括号有多余的
    if(!StackEmpty(&st))
    {
        StackDestory(&st);
        return false;
    }
    //此时栈为空，说明前面的左右括号都匹配了
    else
    {
        StackDestory(&st);
        return true;
    }
}

最后的最后，创作不易，希望读者三连支持

赠人玫瑰，手有余香