【数据结构与算法经典例题】括号匹配问题

            💓 博客主页：倔强的石头的CSDN主页

             📝Gitee主页：倔强的石头的gitee主页

   ⏩ 文章专栏：《数据结构与算法经典例题》C语言

    期待您的关注

一、问题描述

二、解题思路

🍃破解之道

🍃画图举例说明：

三、C语言实现代码

一、问题描述

原题来自

20. 有效的括号 - 力扣（LeetCode）

二、解题思路

🍃破解之道

括号匹配问题是一个比较有实际意义的问题，

问题要求将三种类型括号匹配，其中包括顺序匹配和数量匹配

使用栈的后进先出结构可以很好的解决这个问题:
遍历字符串
遇到左括号则压栈等待右括号匹配；
遇到右括号先进行判断，首先判断栈是否为空，如果为空则不可能完成匹配，直接判定无效

上述判定不成立再进行下列判断
如果此时栈顶的数据是与右括号匹配的左括号，则出栈，否则直接判定无效（顺序不匹配）
当字符串遍历完成时，如果栈为空，则说明括号全部匹配上了；否则说明数量不匹配

关于栈的问题可以阅读前置文章

【数据结构/C语言】使用数组实现栈：原理、步骤与应用-CSDN博客

🍃画图举例说明：

第一种情况：数量顺序完全匹配时

第二种情况：数量匹配，顺序不匹配时

第三种情况：数量不匹配时

三、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;elsereturn false;
}