当前位置: 首页 > article >正文

【C++】每日一练(有效的括号)

本篇博客给大家带来的是用C++语言来解答有效的括号!

🐟🐟文章专栏:每日一练

🚀🚀若有问题评论区下讨论,我会及时回答

❤❤欢迎大家点赞、收藏、分享!

今日思想:不服输的少年啊,请你再努力一下!

题目描述: 

思路:

        我们利用栈来解答,首先遍历数组我们找左括号把他放到栈里,然后再找游括号来看看是否与之匹配。如果遍历完之后栈为空代表匹配完成返回true,反之返回false。

        注意如果没学习过栈的可以看看这篇博客:【C++】数据结构 栈的实现-CSDN博客

代码实例:

typedef char STDataType;
typedef struct Stack
{
	STDataType* arr;
	int top;//指向栈顶的结构
	int capacity;//容量
}ST;

//栈的初始化
void STInit(ST* ps)
{
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}
//入栈-栈顶
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		//空间不够-增容
		int newCapacity = ps->capacity == 0 ? 4 : 2*ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间够了
	ps->arr[ps->top++] = x;
}
//判断栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//拿栈顶的数据
STDataType StackTop(ST* ps)
{
	assert(!StackEmpty(ps));
	return ps->arr[ps->top - 1];
}
//栈的销毁
void STDestroy(ST* ps)
{
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}
//出栈-栈顶
void StackPop(ST* ps)
{
	assert(!StackEmpty(ps));
	--ps->top;
}
bool isValid(char* s) 
{
    ST st;
    STInit(&st);
    char* pi=s;
    //遍历所有的字符串s
    while(*pi !='\0')
    {
        if(*pi=='(' ||*pi=='[' ||*pi=='{')
        {
            StackPush(&st,*pi);
        }
        else
        {
            //找右括号并且与之匹配
            if(StackEmpty(&st))//判断栈是否为空
            {
                STDestroy(&st);
                return false;
            }
            char top=StackTop(&st);
            if((top=='(' && *pi != ')')
            || (top=='[' && *pi !=']')
            || (top=='{' && *pi !='}'))
            {
                STDestroy(&st);
                return false;
            }
            StackPop(&st);
        }
        pi++;
    }
    //栈为空,说明所有的左括号都已经匹配完,反之非有效字符
    bool ret =StackEmpty(&st)?true:false;
    return ret;
}

完!! 


http://www.kler.cn/a/584206.html

相关文章:

  • Matlab 条纹点法向量计算
  • uniapp+Vue3 组件之间的传值方法
  • 基于DeepSeek×MWORKS 2025a的ROM Builder自动化降阶实战
  • 基于qiime2的16S数据分析全流程:从导入数据到下游分析一条龙
  • 计算机就业方向与相关技术
  • 如何修改 Ubuntu 软件源(镜像源)
  • 初阶数据结构(C语言实现)——5.3 堆的应用(1)——堆排序
  • qt5中使用中文报错error: C2001: 常量中有换行符
  • Python入门教程:从零开始学习Python编程
  • Houdini Labs Building Generator入门学习
  • RestTemplate 发送 JSON 请求时为何要手动序列化对象?
  • 用SpringBoot做一个web小案例实现登录
  • 16天 - 单例模式有哪几种实现?如何保证线程安全?什么是策略模式?一般用在什么场景?什么是模板方法模式?一般用在什么场景?
  • Linux中的基本指令(下)
  • 【文献阅读】Zotero 新手完全教程:安装、使用与插件
  • Python Cookbook-4.2 通过列表推导构建列表
  • 【C++】 —— 笔试刷题day_3
  • C++ Primer Plus第十二章课后习题总结
  • 人工智能与我何干
  • 新闻网页信息抽取