一、问题描述
原题来自
二、解题思路
🍃破解之道
括号匹配问题是一个比较有实际意义的问题，
问题要求将三种类型括号匹配，其中包括顺序匹配和数量匹配
使用栈的后进先出结构可以很好的解决这个问题:
遍历字符串
遇到左括号则压栈等待右括号匹配；
遇到右括号先进行判断，首先判断栈是否为空，如果为空则不可能完成匹配，直接判定无效上述判定不成立再进行下列判断
如果此时栈顶的数据是与右括号匹配的左括号，则出栈，否则直接判定无效（顺序不匹配）
当字符串遍历完成时，如果栈为空，则说明括号全部匹配上了；否则说明数量不匹配关于栈的问题可以阅读前置文章
🍃画图举例说明：
第一种情况：数量顺序完全匹配时
第二种情况：数量匹配，顺序不匹配时
第三种情况：数量不匹配时
三、C语言实现代码
C语言需要自己实现栈的数据结构，轮子之前已经造好了，这里就直接CV拿过来了
#include<stdio.h> #include<stdlib.h> #include<assert.h> // 支持动态增长的栈 typedef char STDataType;//对数据类型重命名，方便后期修改类型 typedef struct Stack { STDataType* a; int top; // 栈顶 int capacity; // 容量 }Stack;//定义结构同时重命名 // 初始化栈 void StackInit(Stack* ps) { assert(ps); ps->a = NULL; ps->top = ps->capacity = 0; } // 入栈 void StackPush(Stack* ps, STDataType data) { assert(ps); //判断是否需要扩容 if (ps->top == ps->capacity) { int newcapa = ps->capacity == 0 ? 4 : 2 * (ps->capacity); STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapa); if (tmp == NULL) { perror("realloc\n"); exit(1); } ps->a = tmp; ps->capacity = newcapa; } //确定空间足够之后再插入数据 ps->a[ps->top] = data; ps->top++; } // 出栈 void StackPop(Stack* ps) { assert(ps); assert(ps->top); ps->top--; } // 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); assert(ps->top); return ps->a[ps->top-1]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } //括号匹配问题 bool isValid(char* s) { Stack st; StackInit(&st);//创建一个栈的结构体变量 char* p = s; while (*p) { if (*p == '(' || *p == '[' || *p == '{')//左括号入栈 { StackPush(&st,*p); } if (*p == ')' || *p == ']' || *p == '}')//右括号进行判断 { if (StackEmpty(&st))//此时栈空，可直接判定false { StackDestroy(&st); return false; } else { char tmp = StackTop(&st); StackPop(&st);//栈顶元素出栈 if ((*p == ')' && tmp != '(' )//判断顺序是否匹配 || (*p == ']' && tmp != '[' ) || (*p == '}' && tmp != '{')) return false; } } p++; } if (StackEmpty(&st))//判断数量是否匹配 return true; else return false; }
