绍兴网站制作价格,网站机房建设目的,wordpress网页如何写,服务器安全模式怎么进leetcode20.括号匹配问题
前言#xff1a; #x1f4a5;#x1f388;个人主页:Dream_Chaser#xff5e; #x1f388;#x1f4a5; ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上栈与队列的面试OJ题目 目录
leetcode20.括号匹配问题
1.问题描…leetcode20.括号匹配问题
前言 个人主页:Dream_Chaser ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上栈与队列的面试OJ题目 目录
leetcode20.括号匹配问题
1.问题描述
2.前提准备
3.问题题解 1.问题描述 给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 2.前提准备
栈的实现
#pragma once
#includestdlib.h
#includeassert.h
#includestdbool.h
#includestdio.h
typedef int 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;//栈底//top不是下标pst-top 0;//指向栈顶元素的下一个位置pst-capacity 0;}
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;
}void STPush(ST* pst,STDataType x)
{if (pst-top pst-capacity){int newCapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, newCapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail);return;}pst-a tmp;//返回的是realloc出来的内存块的地址pst-capacity newCapacity;//把扩容后的空间大小赋值给栈容量}pst-a[pst-top] x;//先放值pst-top;//再
}void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst-top--;
}STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst-a[pst-top - 1];
}bool STEmpty(ST* pst)//栈为空返回true,不为空返回false
{//assert(pst);//if (pst-top 0)//{// return true;//}//else//{// return false;//}return pst-top 0;
}int STSize(ST* pst)
{assert(pst);return pst-top;
}
3.问题题解
s指向的是右括号,top存储的是左括号st栈顶指针a栈底指针 只要有一次不对应的情况那么程序直接返回false字符串遍历结束若栈不为空直接返回false在比较过程中若遇到栈为空可是此时字符串未遍历完直接返回false 第一种情况:左括号多余 第二种情况:括号没有多余但是类型匹配不上 第三种情况:右括号多余 代码实现
bool isValid(char * s){ST st;STInit(st);while(*s)//*s就是输入的那个x的值{//1.左括号入栈if(*s ( || *s [ || *s {){STPush(st, *s); }else{if(STEmpty(st))//栈为空也需要销毁因为它malloc了空间空间在那占用着只是数据没填进去{STDestroy(st);return false;}//右括号出栈匹配char topSTTop(st);STPop(st);//只要有一个不匹配直接返回false//左括号和右括号相等说明不了问题只能说明这一次这一对括号匹配还有其它括号不匹配的//所以要找到不继续的条件if((*s ] top! [)||(*s ) top !()||(*s} top!{)){STDestroy(st);return false;}}s;//字符指针的移动}bool retSTEmpty(st);//栈不为空那就是falseSTDestroy(st);return ret;
}
代码执行 本文结束若有错误欢迎改正谢谢支持
