【20. 有效的括号】

---

一、题目描述

题目链接

---

二、做题思路

1.左括号，入栈
2.右括号，左括号出栈跟右括号匹配

---

三、题目代码

typedef char STDataType;
typedef struct Stack
{
    
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps)
{
    
    assert(ps);
    ps->a=NULL;
    ps->top=0;
    ps->capacity=0;
}
void StackDestroy(ST* ps)
{
    
    assert(ps);
    free(ps->a);
    ps->a=NULL;
    ps->top=ps->capacity=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->a,sizeof(STDataType)*newcapacity);
        if(tmp==NULL)
        {
    
            exit(-1);
        }
        else
        {
    
            ps->a=tmp;
            ps->capacity=newcapacity;
        }
    }
    ps->a[ps->top]=x;
    ps->top++;
}
bool StackEmpty(ST* ps)
{
    
    assert(ps);
    return ps->top==0;
}
void StackPop(ST* ps)
{
    
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}
STDataType StackTop(ST* ps)
{
    
    assert(ps);
    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
        {
    
            //遇到右括号了，但是栈里面没有数据，说明
            //前面没有左括号，不匹配，返回false s="]"
            if(StackEmpty(&st))
            {
    
                //[{()}]],这种情况虽然栈是空但入过数据，栈是了开辟空间的
                //所以要销毁，防止内存泄露
                StackDestroy(&st);
                return false;
            }
            STDataType top=StackTop(&st);
            StackPop(&st);
            if((*s == ')' && top != '(')
             ||(*s == '}' && top != '{')
             ||(*s == ']' && top != '['))
            {
    
                //如果s="[[}]",到这里栈里只剩下[
                //防止内存泄露要销毁函数
                StackDestroy(&st);
                return false;
            }
            s++;
        }
        
    }
    //如果栈不是空，说明栈中还有左括号未出
    //没有匹配。返回是false s="["
    bool ret=StackEmpty(&st);
    StackDestroy(&st);

    return ret;
    
    
}

---

以上是本篇文章的全部内容，如果文章有错误或者有看不懂的地方，多和喵博主交流。互相学习互相进步。如果这篇文章对你有帮助，可以给喵博主一个关注，你们的支持是我最大的动力。