【数据结构算法经典题目刨析（c语言）】括号匹配问题（图文详解）

💓 博客主页：C-SDN花园GGbond

⏩ 文章专栏：数据结构经典题目刨析(c语言)

目录

一、题目描述

二、解题思路 

三、代码实现 

---

 

一、题目描述

二、解题思路 

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

使用栈的后进先出结构可以很好的解决这个问题:

根据栈独有的特点，具体操作：1、属于左括号，进行入栈处理。2、属于右括号进行出栈处理，然后进行匹配，不匹配就报错。我们既然选择用C语言来实现，就需要我们自己提前实现一个栈结构

先实现栈 ：

//栈的初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->top = pst->capacity = 0;//top指向栈顶元素的下一个位置}
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;}
void STPush(ST* pst, STDatyType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity=pst->capacity==0 ? 4 : pst->capacity * 2;STDatyType* tmp =(STDatyType*)realloc(pst->a, newcapacity * sizeof(STDatyType));if (tmp == NULL){perror("ralloc fail");return;}pst->capacity = newcapacity;pst->a = tmp;}pst->a[pst->top] = x;pst->top++;
}
//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}
//得到栈顶元素
STDatyType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}
//获取数据个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}

遍历字符串
遇到左括号则压栈等待右括号匹配；
遇到右括号先进行判断，首先判断栈是否为空，如果为空则不可能完成匹配，直接判定无效

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

 

画图举例说明： 

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

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

 

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

 

三、代码实现 

typedef char STDatyType;
typedef struct Stack
{STDatyType* a;int top;int capacity;}ST;
//栈的初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->top = pst->capacity = 0;//top指向栈顶元素的下一个位置}
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;}
void STPush(ST* pst, STDatyType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity=pst->capacity==0 ? 4 : pst->capacity * 2;STDatyType* tmp =(STDatyType*)realloc(pst->a, newcapacity * sizeof(STDatyType));if (tmp == NULL){perror("ralloc fail");return;}pst->capacity = newcapacity;pst->a = tmp;}pst->a[pst->top] = x;pst->top++;
}
//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}
//得到栈顶元素
STDatyType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{assert(pst);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;}//栈不为空STDatyType top=STTop(&st);if(*s==')'&&top!='('||*s==']'&&top!='['||*s=='}'&&top!='{'){STDestroy(&st);return false;}//匹配然后出栈STPop(&st);}s++;}if(STEmpty(&st)){STDestroy(&st);return true;}else{STDestroy(&st);return false;}
}