文章目录
（1）题目描述（2）解题思路（1）题目描述
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
示例1：
输入：s = “( )”
输出：true
示例2：
输入：s = “( ) [ ] { }”
输出：true
示例3：
输入：s = “( ]”
输出：false
示例4：
输入：s = “( [ ) ]”
输出：false
示例5：
输入：s = “{ [ ] }”
输出：true
（2）解题思路
利用栈的性质解决此题
首先实现一个栈
然后遍历字符串，如果遇到左括号（'('，'{'，'['），将其压入栈中，如果遇到右括号（'）'，'}'，']'），将当前栈顶的左括号出栈，与其匹配，看是否是一对，若匹配失败，则返回false，匹配成功，则继续遍历字符串后面的字符。
两种特殊情况：
（1）字符串中全是左括号，全部入栈了，遍历结束后，需要对栈判空一下，若不为空，返回false
（2）字符串中全是右括号，没有左括号则栈为空，所以在遍历字符串遇到右括号时需要判断一下当前栈是否为空，若为空，返回false
图解算法（示例2）：
图解算法（示例5）：代码如下首先实现一个栈：
//定义可以动态增长的栈typedef struct Stack{char* a;int top;int capacity;}Stack;//初始化栈void StackInit(Stack *ps){assert(ps);ps->a = NULL;ps->top = -1;ps->capacity = 0;}//销毁栈void StackDestroy(Stack *ps){assert(ps);if(ps->a){free(ps->a);}ps->a = NULL;ps->top = -1;ps->capacity = 0;}//入栈void StackPush(Stack *ps, char x){assert(ps);if(ps->top == ps->capacity - 1) //检查栈的容量是否已满{//扩容int newcapacity = (ps->capacity == 0) ? 4 : 2 * (ps->capacity);char* temp = realloc(ps->a, newcapacity * sizeof(char));if(temp == NULL){perror("realloc");exit(-1);}ps->a = temp;ps->capacity = newcapacity; //更新容量}ps->top++;ps->a[ps->top] = x;}//出栈void StackPop(Stack *ps){assert(ps);assert(ps->top != -1); //栈不能为空ps->top--;}//获取栈顶元素char StackTop(Stack *ps){assert(ps);return ps->a[ps->top];}//检查栈是否为空bool StackEmpty(Stack *ps){assert(ps);return ps->top == -1;}
核心代码：
bool isValid(char *s){Stack s1;StackInit(&s1);while(*s){if(*s == '(' || *s == '[' || *s == '{') //当前字符为左括号{StackPush(&s1, *s); //入栈}else //当前字符为右括号{if(StackEmpty(&s1)) //如果栈为空，说明没有左括号，则返回false{return false;}char ch = StackTop(&s1);//获取栈顶元素StackPop(&s1);//栈顶元素出栈if((*s == ')' && ch != '(') //当前字符与栈顶元素未匹配成功，返回false|| (*s == ']' && ch != '[')|| (*s == '}' && ch != '{')){return false;}}s++;}//有可能字符串中全是左括号，全部入栈了，所以需要判空一下，若不为空返回falsereturn StackEmpty(&s1); //检测栈是否为空}
上面核心代码，有一个小小的问题，没有销毁栈，可能会造成内存泄漏。
我们来改进一下：用一个布尔变量 match 来记录下返回值 true / false，最后先销毁栈，再返回值。
bool isValid(char *s){Stack s1;StackInit(&s1);bool match = true; //记录函数返回值while(*s){if(*s == '(' || *s == '[' || *s == '{') //当前字符为左括号{StackPush(&s1, *s); //入栈}else //当前字符为右括号{if(StackEmpty(&s1)) //如果栈为空，说明没有左括号，则返回false{match = false;break;}char ch = StackTop(&s1);//获取栈顶元素StackPop(&s1);//栈顶元素出栈if((*s == ')' && ch != '(') //当前字符与栈顶元素未匹配成功，返回false|| (*s == ']' && ch != '[')|| (*s == '}' && ch != '{')){match = false;break;}}s++;}//match为true，有可能因为字符串中全是左括号，全部入栈了，所以需要判空一下，若不为空返回falseif(match == true){match = StackEmpty(&s1);}StackDestroy(&s1); //销毁栈return match;}
大家快去动手练习一下吧！
