题目描述
题目来源：Leetcode20.有效的括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。
解题思路：
该题是栈的典型应用，满足后进先出的规则（后入栈的前括号将优先与先出现的后括号相匹配）。
遍历字符串，遇到前括号直接入栈。遇到后括号，判断该后括号与栈顶的前括号是否匹配（若此时栈为空，则字符串无效），若不匹配则字符串无效；若匹配则删除栈顶元素，继续遍历字符串，直到字符串遍历完毕。当字符串遍历完后，检测栈是否为空，若为空，则字符串有效，若不为空，说明有前括号未匹配，字符串无效。
代码解决：
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdbool.h> //链接： //https ://leetcode.cn/problems/valid-parentheses/ typedef char STDataType;//栈中存储的元素类型 typedef struct Stack { STDataType* a;//栈 int top;//栈顶 int capacity;//容量，方便增容 }Stack; //初始化栈 void StackInit(Stack* pst) { assert(pst); pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);//初始化栈可存储4个元素 pst->top = 0;//初始时栈中无元素，栈顶为0 pst->capacity = 4;//容量为4 } //销毁栈 void StackDestroy(Stack* pst) { assert(pst); free(pst->a);//释放栈 pst->a = NULL;//及时置空 pst->top = 0;//栈顶置0 pst->capacity = 0;//容量置0 } //入栈 void StackPush(Stack* pst, STDataType x) { assert(pst); if (pst->top == pst->capacity)//栈已满，需扩容 { STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } pst->a = tmp; pst->capacity *= 2;//栈容量扩大为原来的两倍 } pst->a[pst->top] = x;//栈顶位置存放元素x pst->top++;//栈顶上移 } //检测栈是否为空 bool StackEmpty(Stack* pst) { assert(pst); return pst->top == 0; } //出栈 void StackPop(Stack* pst) { assert(pst); assert(!StackEmpty(pst));//检测栈是否为空 pst->top--;//栈顶下移 } //获取栈顶元素 STDataType StackTop(Stack* pst) { assert(pst); assert(!StackEmpty(pst));//检测栈是否为空 return pst->a[pst->top - 1];//返回栈顶元素 } //获取栈中有效元素个数 int StackSize(Stack* pst) { assert(pst); return pst->top;//top的值便是栈中有效元素的个数 } /*---以上代码是栈的基本功能实现，以下代码是题解主体部分---*/ bool isValid(char* s) { Stack st;//创建一个栈 StackInit(&st);//初始化栈 char* cur = s; while (*cur) { //前括号统一进栈 if (*cur == '(' || *cur == '[' || *cur == '{') { StackPush(&st, *cur); cur++; } else { //若遇到后括号，且栈为空，则字符串无效 if (StackEmpty(&st)) { StackDestroy(&st); return false; } //获取栈顶元素 char top = StackTop(&st); //后括号与栈顶的前括号不匹配 if (top == '(' && *cur != ')' || top == '{' && *cur != '}' || top == '[' && *cur != ']') { StackDestroy(&st); return false; } //匹配 else { StackTop(&st); cur++; } } } //检测栈是否为空 bool ret = StackEmpty(&st); StackDestroy(&st); //返回结果 return ret; }
结果与总结：
通过所有示例，问题得到解决。
