有效的括号
OJ链接
思路
- 要注意进行顺序匹配的时候，要让右括号和栈顶元素匹配，匹配了一个以后就要让栈顶元素出栈！！
在顺序匹配时，要用 *s == ']' && top != '[' 像这样的不等号，而不能用==，因为就一个匹配上的时候不能直接返回true，但如果有一个匹配不上，就可以直接返回false。
- 要注意数量匹配问题，要考虑全面。
①左括号多，右括号少的问题。如果右括号都匹配完了，栈里还有元素，即不为空，那么就返回false。
②左括号少，右括号多的问题。如果右括号还没有匹配完栈就空了，那么就返回false。
⭐一定要注意内存泄漏问题！return 之前都必须STDestroy(&st)，一定要先销毁再返回！！
代码
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);
STDatatype STTop(ST* pst);
bool STempty(ST* pst);
int STSize(ST* pst);#define _CRT_SECURE_NO_WARNINGS 1void STInit(ST* pst)
{assert(pst);pst->a = 0;pst->top = 0;pst->capacity = 0;
}void Createcapacity(ST* pst)
{//扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;ST* tmp = (ST*)realloc(pst->a, sizeof(ST) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}
}void STPush(ST* pst, STDatatype x)
{assert(pst);Createcapacity(pst);pst->a[pst->top] = x;pst->top++;
}void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}STDatatype STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}bool STempty(ST* pst)
{assert(pst);return pst->top == 0;//为0就是true 为！=0就是为flase
}int STSize(ST* pst)
{assert(pst);return pst->top;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}bool isValid(char* s) {ST st;STInit(&st);while (*s){if (*s == '[' || *s == '(' || *s == '{'){STPush(&st, *s);}else{//右括号比左括号多，数量不匹配if (STempty(&st)){STDestroy(&st);return false;}char top = STTop(&st);STPop(&st);//顺序不匹配if ((*s == ']' && top != '[')|| (*s == '}' && top != '{')|| (*s == ')' && top != '(')){STDestroy(&st);return false;}}++s;}//栈为空是真，返回真。说明数量都匹配 左括号多，右括号少的问题bool ret = STempty(&st);STDestroy(&st);return ret;
}
