题目描述
题目分析
题目给了我们三种括号：（）、{ }、[ ]
这里的匹配包括：顺序匹配和数量匹配
最优的思路就是用栈来解决：
括号依次入栈，当遇到右括号的时候，和他最近的那个左括号匹配，能匹配则返回true，否则false；最近的左括号即为栈顶元素
数组栈我们在之前实现过，直接拿来用就可以了：数组栈的实现-CSDN博客
由于存放的数据是字符，所以这里的STDataType就可以typedef为char
遍历字符串：
- 是左括号就入栈
- 遇到右括号，则取栈顶元素，并pop掉
- 最后如果栈为空则返回true，否则返回false，所以我们还需要判空
- 防止内存泄漏，我们在每次返回false之前都需要Destroy
代码示例
根据这个思路我们就可以写代码了：
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> 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->capacity = 0; pst->top = 0; } //销毁 void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; 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, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } 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); /*if (pst->top == 0) { return true; } else { return false; }*/ return pst->top == 0; } //栈的元素个数 int STSize(ST* pst) { assert(pst); return pst->top; } 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; }
