20.有效的括号（LeetCode）

思路：用栈的后进先出的特性，来完成题目的要求 

因为C++有库，可以直接用，而C语言没有，所以我们直接把写好的栈拷贝上来用。  

首先，完成框架的搭建 

其次，再实现循环内的部分。1.左括号入栈 2.右括号出栈匹配 

这里在右括号匹配的判断，要注意不要写成两个都相等，这样不能说明全都匹配成功，所以就写成两边不相等，满足则直接return false，不满足则继续循环 

每次循环结束，s++。所有循环停止后，没有return false，则return true 

看起来好像没有什么问题，对吧？ 

其实，上述只适用于左右括号数量相等的场景，我们还要考虑两种特殊情况 ：

1.左括号多于右括号

2.右括号多于左括号

左括号多于右括号时，循环结束，栈内元素个数不为0，则用STEmpty判断一下 ，如果为空，与之前相同，返回true，如果不为空，则返回false

右括号多于左括号时，在循环内部，直到栈已经空了，还有右括号要匹配，那么此时也直接返回false 

完整代码如下：

typedef char 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);void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->top = 0;//top指向栈顶元素的下一个位置pst->capacity = 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->top = pst->capacity = 0;
}void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newCapacity;}pst->a[pst->top++] = x;
}void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst->top--;
}STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst->a[pst->top - 1];
}bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}int STSize(ST* pst)
{assert(pst);return pst->top;
}bool isValid(char* s)
{ST st;STInit(&st);while (*s){//1.左括号入栈//2.右括号出栈匹配if (*s == '('||*s == '['||*s == '{'){STPush(&st, *s);}else{//解决右括号多于左括号的问题if (STEmpty(&st)){STDestroy(&st);return false;}char top = STTop(&st);STPop(&st);if ((top != '(' && *s == ')')||(top != '[' && *s == ']')||(top != '{' && *s == '}')){STDestroy(&st);return false;}}s++;}//解决左括号多于右括号的问题bool ret = STEmpty(&st);STDestroy(&st);return ret;
}