题目地址->有效的括号

题目
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false

通过示例可以得到的消息是左右括号必须匹配，这里我们用之前学到的栈来完成这道题目

思路

题目意思为，如果有一个左括号，那必须有一个右括号与之对应
看到括号要对应出现，大家可能会想到去数括号的个数来做这道题
但这样是错误的💔
例如：

（{）}

这样的括号是不能通过数个数来判断是否正确的
我们只用栈来做这个题

利用栈来解答这道题

题目中给到的函数接口是这样的

bool isValid(char * s){}

说明 s 是字符串，里面只会存放括号

我们需要判断括号的开口反向就好了
如果是左括号那就入栈

如果是右括号就，与栈顶元素判断

栈的代码

栈是我们之前讲过的
地址：栈和队列讲解

typedef char STDatatype;typedef struct Stack
{STDatatype* a;int top;int capacity;
}Stack;void STInit(Stack* ps)
{assert(ps);ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);if (ps->a == NULL){printf("malloc fail");return;}ps->capacity = 4;ps->top = 0;
}// 销毁
void STDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//插入
void STPush(Stack* ps, STDatatype x)
{assert(ps);if (ps->top == ps->capacity){STDatatype* tmp = (STDatatype*)realloc(ps->a,sizeof(STDatatype) * ps->capacity * 2);if (tmp == NULL){perror("malloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}//判断是否为空
bool STEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}//删除
void STPop(Stack* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}//计算个数
int STSize(Stack* ps)
{assert(ps);return ps->top;
}//出栈
STDatatype STTop(Stack* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

题目接口：

bool isValid(char * s){Stack st;STInit(&st);while(*s){switch(*s){case '{':case '[':case '(':{STPush(&st,*s);s++;break;}case '}':case ']':case ')':{if(STEmpty(&st)){STDestroy(&st);return false;}char top = STTop(&st);STPop(&st);if((*s == '}' && top != '{') || (*s == ']' && top != '[') || (*s == ')' && top != '(')){STDestroy(&st);return false;              }else{s++;}}}}bool ret = STEmpty(&st);STDestroy(&st);return ret;
}