苏州网站设计kgwl,建设网站需要用到哪些技术人员,安阳贴吧,北京软件开发哪家好题目描述
题目链接#xff1a;20. 有效的括号 - 力扣#xff08;LeetCode#xff09; 题目分析
题目给了我们三种括号#xff1a;#xff08;#xff09;、{ }、[ ]
这里的匹配包括#xff1a;顺序匹配和数量匹配
最优的思路就是用栈来解决#xff1a; 括号依次入栈…题目描述
题目链接20. 有效的括号 - 力扣LeetCode 题目分析
题目给了我们三种括号、{ }、[ ]
这里的匹配包括顺序匹配和数量匹配
最优的思路就是用栈来解决 括号依次入栈当遇到右括号的时候和他最近的那个左括号匹配能匹配则返回true否则false最近的左括号即为栈顶元素 数组栈我们在之前实现过直接拿来用就可以了数组栈的实现-CSDN博客
由于存放的数据是字符所以这里的STDataType就可以typedef为char 遍历字符串
是左括号就入栈遇到右括号则取栈顶元素并pop掉最后如果栈为空则返回true否则返回false所以我们还需要判空防止内存泄漏我们在每次返回false之前都需要Destroy
代码示例
根据这个思路我们就可以写代码了
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;//标识栈顶位置int capacity;
}ST;
//声明//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//返回栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//栈的元素个数
int STSize(ST* pst);//定义//初始化
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;pst-top 0;
}
//销毁
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}
//入栈
void STPush(ST* pst, STDataType x)
{assert(pst);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 STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}
//返回栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-a[pst-top - 1];
}
//判空
bool STEmpty(ST* pst)
{assert(pst);/*if (pst-top 0){return true;}else{return false;}*/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;}//取栈顶元素char top STTop(st);STPop(st);//匹配if ((*s ) top ! () || (*s ] top ! [) || (*s } top ! {)){STDestroy(st);return false;}}s;}bool ret STEmpty(st);STDestroy(st);return ret;
}
