英文企业网站源码,贵州交通建设集团网站,辽宁网上注册公司流程,网红营销也称为Leetcode刷题之有效的括号#xff08;C语言版#xff09; 一、题目描述二、题目测试用例三、题目分析四、完整代码 一、题目描述
20、有效的括号
给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是… Leetcode刷题之有效的括号C语言版 一、题目描述二、题目测试用例三、题目分析四、完整代码 一、题目描述
20、有效的括号
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。有效字符串需满足①、左括号必须用相同类型的右括号闭合。
②、左括号必须以正确的顺序闭合。
③、每个右括号都有一个对应的相同类型的左括号。二、题目测试用例 三、题目分析
本题是要将左括号与右括号相匹配的进行闭合所以我们想到采用“栈”的先进后出特性来进行数据的存放操作。所以我们先要写一个栈出来包括栈的创建栈的销毁等许多的基础操作。如果大家忘记了栈的相关操作如何去写可以看我之前的文章《数据结构——栈的详细介绍》。写好栈之后我们对于本道题的解题思路便是 ①、左括号入栈 if(*s(||*s{||*s[){PushST(st,*s);}②、右括号出栈顶元素与其进行比较 这里需要注意的是如果当前只有一个任意的右括号那么就没有可能出栈与其进行匹配操作所以在此要对栈进行判空保证当前栈内存在元素。如果当前栈内没有元素便要对栈进行销毁操作以防止内存的泄漏。 else{//判断栈当前是否为空if(STEmpty(st)){//注意在此需要防止内存泄漏//销毁栈DestoryST(st);return false;}//判断匹配问题char topTopST(st);//对栈顶元素进行出栈更新栈顶元素PopST(st);if((*s]top![)||(*s}top!{)||(*s)top!()){//注意在此需要防止内存泄漏//销毁栈DestoryST(st);return false;}}③、返回值 bool retSTEmpty(st);查看当前栈内是否还存在其他的元素如果没有则返回true,否则返回false。
四、完整代码
//定义数据类型
typedef char STDatatype;typedef struct STack
{STDatatype* a;//数组int capacity;//容量int top;//栈顶元素的下一个
}ST;//初始化
void InitST(ST* pst);
//销毁
void DestoryST(ST* pst);
//压栈
void PushST(ST* pst, STDatatype x);
//出栈
void PopST(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取栈顶元素
STDatatype TopST(ST* pst);
//获取栈的size
int STSize(ST* pst);
//初始化
void InitST(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;//栈顶元素的下一个位置pst-top 0;
}
//销毁
void DestoryST(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-capacity pst-top 0;
}
//压栈
void PushST(ST* pst, STDatatype x)
{if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDatatype *tmp (STDatatype*)realloc(pst-a, sizeof(STDatatype) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}//插入数据pst-a[pst-top] x;pst-top;
}
//出栈
void PopST(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst-top--;
}
//判空
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}
//获取栈顶元素
STDatatype TopST(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst-a[pst-top-1];
}
//获取栈的size
int STSize(ST* pst)
{assert(pst);return pst-top;
}
bool isValid(char* s)
{ST st;//初始化InitST(st);//解题思路①左括号入栈 ②右括号出栈while(*s){if(*s(||*s{||*s[){PushST(st,*s);}else{//判断栈当前是否为空if(STEmpty(st)){//注意在此需要防止内存泄漏//销毁栈DestoryST(st);return false;}//判断匹配问题char topTopST(st);//对栈顶元素进行出栈更新栈顶元素PopST(st);if((*s]top