力扣刷题 -- 20.有效的括号

1. 题目

2. 思路分析 

第一步:先看题目理解大意。题目中说左括号必须遇到对应的右括号匹配且闭合顺序必须正确。即（）配对，{ }配对，[ ]配对。

第二步：观察示例，我们可以发现示例三是回文结构，示例四又是对称结构，看到这里还是没有思路。再想想

第三步：既然左括号要遇到右括号才能进行匹配，那如果我遍历字符串：遇到左括号就入栈，遇到右括号我就将左括号拿出来进行匹配！欸，这个思路好像可以！

到这里其实你的思路就基本正确了：

正确的思路如下： 

遍历字符串，遇到左括号就入栈，当遇到右括号时：取栈顶元素进行匹配，匹配就出栈。如果遍历完后，如果栈为空则字符串有效；否则无效！！

注意：有几种特殊情况我们需要考虑到：

3. 实现代码 

typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top;//栈顶（相当于size）int capacity;//栈的大小
}ST;
//初始化
void StackInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}
//销毁
void StackDestroy(ST* ps)
{assert(ps);if (ps->arr != NULL){free(ps->arr);ps->arr = 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 : 2 * ps->capacity;STDataType* temp = realloc(ps->arr, newcapacity * sizeof(STDataType));if (temp == NULL){perror("realloc fail!");exit(1);}else//扩容成功{ps->arr = temp;ps->capacity = newcapacity;}}//空间够了，进行入栈ps->arr[ps->top] = x;ps->top++;
}
//判断栈顶为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//出栈
void StackPop(ST* ps)
{assert(ps);if (!StackEmpty(ps)){ps->top--;}
}//获取栈顶元素
STDataType Stacktop(ST* ps)
{assert(ps);return ps->arr[ps->top-1];
}
//获取栈顶元素有效个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}
/栈的结构和相关方法///
bool isValid(char* s) {STDataType* pi=s;ST pq;while(*pi!='\0'){//遍历字符串，碰到左括号进行入栈if(*pi=='('||*pi=='{'||*pi=='['){StackPush(&pq,*pi);//入栈pi++;}//遇到右括号else{//先判断栈是否为空if(StackEmpty(&pq)){return false;}else{//取栈顶元素，看是否匹配int top = Stacktop(&pq);if(*pi==')'&&top!='('||*pi==']'&&top!='['||*pi=='}'&&top!='{'){return false;}//匹配else{StackPop(&pq);//出栈pi++;}}}}if(StackEmpty(&pq)){return true;}else{return false;}
}