“寻寻觅觅冷冷清清凄凄惨惨戚戚”
“三杯两盏淡酒，怎敌他晚来风急”
这道题是括号匹配问题，典型对 栈的应用的题目。
如何创建一个顺序栈在前面的博文已经实现：传送门。
题目描述
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
题目链接
题目分析
括号匹配问题，典型的对数据结构 栈的应用。
以我现在初学数据结构的水平，LeetCode虽然表明它是个简单题，但对我来说并不简单，知识储备量不够多，用纯C解决的话，很繁琐。
我的思路是先需要创建一个顺序结构的栈，然后用栈的基本功能如：压栈(StackPush)，出栈(StackPop)，得到栈顶的元素(StackTop)等功能 来完成这道题。
思路：
1.遍历整个字符串“ ‘(’，’)’，’{’，’}’，’[’，’]’ ”。
2.在遍历的过程中如果遇到左括号’(’，或者’{’，或者’[’。进行压栈操作(StackPush)。
3.如果遇到右括号’)’，或者’}’，或者’]’，则进行访问栈顶元素的值的操作(StackTop)，如果栈顶的左括号和其中之一的右括号匹配，则进行出栈操作(StackPop)。
4.直到字符串越界循环结束。
代码实现
注意：在实现的过程中，需要注意极端情况。
普通情况正常人都能想到。而极端情况就不一定了。
而且题目的实例中可没有给哦。
1.假如只有一个左括号‘（’呢？
//提示：只有一个左括号时，栈就不为空了。
2.假如只有一个右括号‘）’呢？
//提示：只有一个右括号时栈为空。
/*********** *结构体创建 ***********/ typedef char STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; /*********** *函数的声明 ***********/ //初始化结构体 void StackInit(ST* ps); //销毁结构体 void StackDestroy(ST* ps); //压栈 void StackPush(ST* ps, STDataType x); //出栈 void StackPop(ST* ps); //得到栈顶的值 STDataType StackTop(ST* ps); //判断栈是否为空 bool StackEmpty(ST* ps); //得到栈的长度 int StackSize(ST* ps); /*********** *函数的定义 ***********/ //初始化结构体 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0; } //销毁结构体 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = 0; ps->top = 0; } //压栈 void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* new = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity); if (new == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = new; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++; } //出栈 void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } //访问栈顶元素 STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } //判断栈是否为空 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } //得到栈的长度 int StackSize(ST* ps) { assert(ps); return ps->top; } /*********** *题目函数接口 ***********/ bool isValid(char* s) { ST st; //创建栈，否则后续压栈等操作无法实现 StackInit(&st); while (*s) { if (*s == '(' || *s == '{' || *s == '[') { StackPush(&st, *s); s++; } else { //只有一个右括号时，栈为空。直接return false if (StackEmpty(&st)) { return false; } char top = StackTop(&st); if (*s == ')' && top == '(' || *s == '}' && top == '{' || *s == ']' && top == '[') { StackPop(&st); s++; } else { return false; } } } //处理只有一个左括号 if (!StackEmpty(&st)) { return false; } return true; //销毁栈，拒绝内存泄漏 StackDestroy(&st); }
