视频网站如何做弹幕,介绍西安网页设计,wordpress写网页教程,WordPress仿虎嗅主题#x1f493; 博客主页#xff1a;C-SDN花园GGbond ⏩ 文章专栏#xff1a;数据结构经典题目刨析(c语言) 目录
一、题目描述
二、解题思路
三、代码实现 一、题目描述 二、解题思路 问题要求将三种类型括号匹配#xff0c;其中包括顺序匹配和数量匹配 使用栈的后进先… 博客主页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 newcapacitypst-capacity0 ? 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 newcapacitypst-capacity0 ? 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 topSTTop(st);if(*s)top!(||*s]top