河南手机网站建设公司,宁波网站建设公司哪有,套模板做网站电话,装修网站建设网一.前言 如果想要使用C语言来解决这道题——有效的括号#xff1a;https://leetcode.cn/problems/valid-parentheses/description/我们必须要借用上一篇我们所讲的内容——栈的实现#xff1a;https://blog.csdn.net/yiqingaa/article/details/138923750?spm1001.2014.3001.…一.前言 如果想要使用C语言来解决这道题——有效的括号https://leetcode.cn/problems/valid-parentheses/description/我们必须要借用上一篇我们所讲的内容——栈的实现https://blog.csdn.net/yiqingaa/article/details/138923750?spm1001.2014.3001.5502 因为在C语言环境下力扣不会主动帮你实现栈需要用户自己手动创建栈。但是在C环境下力扣会主动为我们实现栈。 2.正文
1.1题目描述 1.2题目分析
1.21 题目想让用户干什么 这道题为我们用户提供了一个字符串s。我们需要编写程序来判断所给字符串s中相同类型的左括号与右括号是否一 一匹配。如果匹配正确就返回true。匹配不正确就返回false。 1.22 如何求解题目 这道题我们可以运用栈的知识面来求出这道题。 我们可以先创建一个栈变量st然后让字符串s逐一遍历字符如果遍历过程中字符是‘’ ‘[’ ‘{’ 都可以将它们尾插到我们栈当中。如果在遍历过程中不是‘’ ‘[’ ‘{’ 而是‘)’ ‘]’ ‘}’我们可以调用之前写好的函数功能——取出栈顶元素 STDataType STTop(ST* ps) 这里的SLDataType是我们栈数据类型可能是int、char或者其他类型。调出可能之前存入栈的字符‘’ ‘[’ ‘{’ 并与遍历字符作对比。这里我暂且将取出栈顶的元素用变量top接受。我们就有取出栈顶元素与现在遍历字符的关系 if ((top ( *s ! )) || (top { *s ! }) || (top [ *s ! ])) 满足上面其中一个条件我们就可以说明相同类型的左括号与右括号没有一 一匹配。我们直接返回false即可。 值得注意的是:在返回true或者false之前都要对栈进行销毁处理——void STDestroy(ST* ps) 1.3代码实现
typedef int STDataType;
struct Stack
{STDataType* a;int top;int capacity;
};
typedef struct Stack ST;
void STInit(ST* ps);//栈的初始化
void STDestroy(ST* ps);//栈的销毁void STPush(ST*PS,STDataType x);//入栈
void STPop(ST* ps);//出栈STDataType STTop(ST* ps);//取栈顶的数据bool STEmpty(ST*ps);//判空int STSize(ST* PS);//获取数据个数
void STInit(ST *ps)//栈的初始化
{assert(ps);ps-a NULL;ps-capacity ps-top 0;
}
void STDestroy(ST* ps)//栈的销毁
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}
void STPush(ST* ps, STDataType x)//入栈
{assert(ps);if (ps-capacity ps-top){int newcapacity ps-capacity 0 ? 10 : ps-capacity*2;STDataType* tmp (STDataType*)realloc(ps-a, newcapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail!);return;} ps-a tmp;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top;
}
void STPop(ST* ps)//删除栈顶元素
{assert(ps);assert(ps-a);ps-top--;
}
STDataType STTop(ST* ps)//取出栈顶元素
{assert(ps);assert(ps-top 0);return ps-a[ps-top-1];
}
bool STEmpty(ST* ps)//判断栈内元素是否为空
{assert(ps);if (ps-top 0)return true;return false;
}
int STSize(ST* ps)//获取数据个数
{assert(ps);return ps-top ;
}
bool isValid(char* s)
{ST st;
STInit(st);
while (*s)
{if (*s ( || *s { || *s [){STPush(st, *s);}else{if(STEmpty(st))//这一步是必须的因为如果栈为空且*s是) ] }说明
//题目给出的字符可能是这样的“)”、“(){}]”。类似这种情况都是不符合题意的情况。return false;char top STTop(st);STPop(st);//这里一定要进行尾部栈顶元素删除以便遍历字符和栈内字符能够对的上if ((top ( *s ! )) ||(top { *s ! }) ||(top [ *s ! ])){return false;}}s;
}
if (st.top ! 0)return false;
STDestroy(st);
return true;
}
三.结言
今天的题目分享就到此结束了觉得对你有所帮助的同学能不能求一个三连。
