Leetcode-有效的括号

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流
作者简介:
CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
掘金LV3用户 https://juejin.cn/user/1381426159953960
阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目

https://leetcode-cn.com/problems/valid-parentheses/

由题意可知

• 字符串仅由左右括号组成
• 左括号：（{[
• 右括号： )}]

错误想法1：统计左右括号的数量，如果左括号数量 == 右括号数量 返回true

例如：([)] ->这样左右括号数量虽然一样，但是并不匹配

• 正确想法： 使用栈的后进先出特性
• 遍历字符串s，如果为碰到左括号就进栈，s++往后走
• 如果碰到右括号，就出栈顶元素进行比较，如果不匹配，返回false，如果匹配，s++往后走
• ==注意：返回前都要先销毁栈空间==

特殊情况：

１.碰到右括号，要出栈顶元素时，栈中无元素了　->匹配失败

２.最后遍历完字符串，若栈中还有元素　->匹配失败

实现的接口：

bool isValid(char * s)
{
    //空字符串
    if(*s == '\0')
    {
        return false;
    }
    //空指针
    if(s == NULL)
    {
        return false;
    }

    ST st;//创建栈
    StackInit(&st);//栈初始化

    //遍历字符串
    while(*s)
    {
        //碰到左括号就进栈
        if(*s == '{' 
        || *s == '[' 
        || *s == '(')
        {
            StackPush(&st,*s);//左括号进栈
            s++;//ｓ向后走
        }
        else
        {
            //碰到右括号，出栈顶的左括号进行匹配

            //如果栈中没有元素与右括号进行匹配->栈为空，匹配失败
            if(StackEmpty(&st))
            {
                //返回前要释放栈
                StackDestroy(&st);
                return false;
            }
            else
            {
                STDataType tmp = StackTop(&st);  //得到栈顶元素进行比较
                StackPop(&st);//弹出栈顶元素
                
                //不匹配则返回false
                if(tmp != '{' && *s =='}'
                || tmp != '[' && *s ==']' 
                || tmp != '(' && *s ==')')
                {
                    //返回前要释放栈
                    StackDestroy(&st);
                    return false;
                }
                //如果匹配，则s往后走
                else
                {
                    s++;
                }
            }
        }
    } 

    //如果比较完了之后，还要看栈是否为空，如果栈中还有元素，说明不匹配
    bool tmp = StackEmpty(&st);
    //返回前要释放空间
    StackDestroy(&st);
    return tmp;
}

总的代码

//现在栈存放的是字符
typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

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

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

void StackDestroy(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;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType)*newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

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

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

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

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

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

	/*if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return ps->top == 0;
}

bool isValid(char * s)
{
    //空字符串
    if(*s == '\0')
    {
        return false;
    }
    //空指针
    if(s == NULL)
    {
        return false;
    }

    ST st;//创建栈
    StackInit(&st);//栈初始化

    //遍历字符串
    while(*s)
    {
        //碰到左括号就进栈
        if(*s == '{' 
        || *s == '[' 
        || *s == '(')
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            //碰到右括号，出栈顶的左括号进行匹配

            //如果栈中没有左括号了->栈为空，匹配失败
            if(StackEmpty(&st))
            {
                //返回前要释放栈
                StackDestroy(&st);
                return false;
            }
            else
            {
                STDataType tmp = StackTop(&st);
                StackPop(&st);
                if(tmp != '{' && *s =='}'
                || tmp != '[' && *s ==']' 
                || tmp != '(' && *s ==')')
                {
                    //不匹配
                    //返回前要释放栈
                    StackDestroy(&st);
                    return false;
                }
                else
                {
                    s++;
                }
            }
        }
    } 

    //如果比较完了之后，栈中还有元素，说明不匹配
    bool tmp = StackEmpty(&st);
    //返回前要释放空间
    StackDestroy(&st);
    return tmp;
}