整合营销服务商

电脑端+手机端+微信端=数据同步管理

免费咨询热线：

带你一步实现《栈》（括号匹配问题）

栈的结构及概念

栈是一种特殊的线性表，只允许在固定的一端插入或删除数据，进行插入和删除的一端被称为栈顶，另一端称为栈底。栈中的数据遵循后进先出原则

LIFO（LAST IN FIRST OUT)

一步一步来实现他

//静态的
//#define N 10
//struct stack
//{
//	int  a[N];
//	int top;
//};
typedef int TYPE;
typedef struct Stack
{
	TYPE* a; 	
	TYPE top;
	int capacity;
}ST;

如果还是用静态的数组就太低端了，而且还会遇到容量不够的问题,因为要储存的值的类型有可能会发生变化，所以可以将变量类型定义一下，需要修改时不至于要修改很多地方。

进入正题

void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

判断创建的结构体指针变量是否为空assert

将ps指向的数组先置空，然后将容量设置为0，数据量设置为0。

判空函数

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

还是要检查ps是否有问题，返回一个bool变量，判断是false还是true，如果等于0，就返回true，说明栈内为空。

求栈内元素个数

int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

这个很简单，只需要返回top的值即可。

删除元素

这个很很简单相较于用链表实现

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

即可，当然如果ps指向的top已经是0了就不能再删除了。

添加元素

void STPush(ST* ps, TYPE x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		//ps->capacity *= 2;//当capacity等于零时不好用
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		TYPE* tmp = (TYPE*)realloc(ps->a, sizeof(TYPE) * newcapacity);//判断是否扩容成功
		if (tmp == NULL)
		{
			perror("realloc fail");
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}


void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

判断必不可少，因为内存是malloc过来的，要用free函数将其释放掉，然后恢复到初始化函数时的状态。将容量还有数量全部还原为零。

获取栈顶元素

TYPE STTop(ST* ps) 
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

判断栈内到底有没有元素，这是很重要的，不然会越界访问，然后返回入栈的数量减一下标的元素即可，为什么减一呢，第一个元素，下标为零，懂了吧！

别忘记在STACK.h中声明这几个函数

void STInit(ST* ps);
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps,TYPE x);
//出栈
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
//获取栈顶元素
TYPE STTop(ST* ps);

来测试一波

test.c

#define _CRT_SECURE_NO_WARNINGS
#include "stack.h"
#include 
Test1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);

用栈解决括号匹配问题_利用栈解决括号匹配问题_栈表达式中括号配对问题

	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}
	printf("\n");
	STDestroy(&st);
}

运行后如图

加粗样式

如果有想测验一下的，下边就是代码

Test1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}
	printf("\n");
	STDestroy(&st);
}
int main()
{
	Test1();
	return 0;
}

学习完了栈的定义及实现，上一个重头戏

题目：括号的匹配

在这里插入图片描述

这道题实现起来很不简单，如果没有学习栈相关的知识，我们在判断时会遇到很多阻力，这道题也可以叫做括号的匹配。例如

分析题目要求，仔细分析可以发现，在利用括号开始进行匹配时，如果是右括号（统称）那就入栈，如果是左括号，那就从栈中取出一个元素与其相匹配，如果匹配成功，那就继续向后匹配，如果匹配失败，那就直接返回，并标明匹配错误。

拿出一个测试用例进行解释

在这里插入图片描述

接下来解决逻辑问题

首先，因为我们需要用到栈，可以将上边所讲的栈的实现函数全部复制粘贴进去，然后利用栈的特性来实现大体逻辑。

代码如下

bool isValid(char * s){
    ST st;
    STInit(&st);
    char top;
    while(*s)
    {
        if((*s=='[')||(*s=='(')||(*s=='{'))
        {
            STPush(&st,*s);           
        }
        if(*s==')')
        {
            if(STEmpty(&st))
            {
                return false;
            }
            top=STTop(&st);
            STPop(&st);
            if(top!='(')
            {
                return false;
                STDestroy(&st);
            }
        }
        if(*s=='}')
        {
            if(STEmpty(&st))
            {
                return false;
            }
            top=STTop(&st);
            STPop(&st);
            if(top!='{')
            {
                return false;
                STDestroy(&st);
            }
        }
        if(*s==']')
        {
            if(STEmpty(&st))
            {
                return false;
            }
            top=STTop(&st);
            STPop(&st);
            if(top!='[')
            {
                return false;
                STDestroy(&st);
            }
        }        
        s++;
    }
    bool ret=STEmpty(&st);
    STDestroy(&st);//销毁
    return ret;
}

创建一个结构体指针变量，这里要注意，上边所写的默认是整型数组，将设置的TYPE改成char类型即可。

在循环体中，我们可以选择使用switch case语句，也可以用if else 语句，代码逻辑十分清晰，在遍历数组的过程中，如果是右括号，则直接入栈，如果是左括号，就出栈顶元素与其相匹配，匹配成功，则走到循环体最后s++的位置，进行下一次判断。

也要注意数组是否为空，可以使用判空函数，如果为空就返回true，如果不为空就返回false，如果是空的话，相当于经历循环体后已经没有左括号了，但是如果不为空的话，那就相当于数组中还剩下一些括号，这些括号是没有被匹配的。

例如

{}()[]{{{

经历过循环后，前边的三组已经匹配完成了，然而后边还有三个右括号入栈，这三个括号没有匹配，所以用判空函数判断一下，如果循环之后栈不为空的话，那就说明匹配不成功，返回false。

需要注意的是取出栈顶元素后将栈顶元素删除。

全部代码如下


typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	STDataType top;
	int capacity;
}ST;
void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	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);
	// 11:40
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}
STDataType STTop(ST* ps)
{
	assert(ps);
	// 
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
// bool isValid(char * s)
// {
// }
bool isValid(char * s){
    ST st;
    STInit(&st);
    char top;
    while(*s)
    {
        if((*s=='[')||(*s=='(')||(*s=='{'))
        {
            STPush(&st,*s);           
        }
        if(*s==')')
        {
            if(STEmpty(&st))
            {
                return false;
            }
            top=STTop(&st);
            STPop(&st);
            if(top!='(')
            {
                return false;
                STDestroy(&st);
            }
        }
        if(*s=='}')
        {
            if(STEmpty(&st))
            {
                return false;
            }
            top=STTop(&st);
            STPop(&st);
            if(top!='{')
            {
                return false;
                STDestroy(&st);
            }
        }
        if(*s==']')
        {
            if(STEmpty(&st))
            {
                return false;
            }
            top=STTop(&st);
            STPop(&st);
            if(top!='[')
            {
                return false;
                STDestroy(&st);
            }
        }        
        s++;
    }
    bool ret=STEmpty(&st);
    STDestroy(&st);//销毁
    return ret;
}

7777777,加油！

[Windows] 视频字幕AI自动提取工具 青梧字幕 v0.9.13便携版

哈喽，黑域小伙伴，现在很多同学和 up 主都会拍一些 Vlog 或转载各种各样的视频传到网上分享，然而工作量比较大且较为枯燥的就是给视频加字幕了，而依靠人工去听写制作字幕效率真的很慢。所以说在当今数字化时代，字幕提取通常是影视制作和字幕翻译过程中的重要环节。

但是直接从视频里面提取出硬字幕可不是件容易的事，一两分钟的短视频还好，自己还可以想些办法（如录音转文字）轻松提取文案。尽管现在市面上已经有许多类似的字幕软件或商家提供在线服务，但它们往往收费、限制了提取时长，要么各种套路，实在没意思。

所以这次，我就给大家安利一款跨平台超好用的AI视频字幕智能提取翻译工具，有了这款神器，一键提取视频中你想要的各种文字！

具体我们来打开体验下：

青梧字幕是一款基于 Whisper 的AI字幕提取工具，它通过先进的AI算法和高效的字幕提取技术，能够自动从视频文件中提取字幕内容。

目前暂支持 Windows 及 Mac（M及intel系列处理器）系统环境，支持识别中、英、日、韩等99种语言，支持srt/vtt/lrc等常见字幕格式。

[Windows] 视频字幕AI自动提取工具 青梧字幕 v0.9.13便携版

非常适合用于无字幕版本的美、英、日、澳、欧视频加工，只需依赖特定模型自动识别语种进而智能提取字幕，无任何功能限制。

但首次使用需要微信“扫一扫”授权登录。

[Windows] 视频字幕AI自动提取工具 青梧字幕 v0.9.13便携版

登录成功后：

软件就只有这一个首页，整个界面干净整洁，没有一丝多余的功能，点击“开始提取字幕”即可将视频文件导入进去。

[Windows] 视频字幕AI自动提取工具 青梧字幕 v0.9.13便携版

选择语言模型：

字幕提取安卓版软件下载_字幕提取神器下载_字幕提取软件安卓版

然后弹出“提取设置”页，如果有安装N卡的朋友也可同步勾选上，加快提取进度（默认不带模型，需自行导入，但也可在页面内下载）

[Windows] 视频字幕AI自动提取工具 青梧字幕 v0.9.13便携版

多种模型：

该软件拥有多种模型，不同的模型适应不同的应用场景，大家可以根据自身需求选择最合适的模型以达到最佳的效果。

无论是大型模型还是小型模型，分析的精确度往往与模型的大小成正比。当然，模型越大，效果越好，对电脑的性能要求也就越高。

[Windows] 视频字幕AI自动提取工具 青梧字幕 v0.9.13便携版

我这里就以小模型下载演示了，下载完成后右上角导入该模型即可。

语言默认自动检测，提示词和每句话最大字数可不设，然后点击“确定提取”即可。不出几秒，字幕都被显示出来了。

[Windows] 视频字幕AI自动提取工具 青梧字幕 v0.9.13便携版

与其说是“提取”，倒不如说是利用上述模型将视频内的音频自动识别，生成为对应的语种字幕，实现提取及翻译后续处理操作。

它还可以通过跟踪字幕：

做到确保无论视频内容如何变化，字幕都可以精准贴合，防止错位或丢失，并保证字幕同音频一致。

[Windows] 视频字幕AI自动提取工具 青梧字幕 v0.9.13便携版

除了可以提取字幕：

字幕提取软件安卓版_字幕提取安卓版软件下载_字幕提取神器下载

这款软件还可以进行简单的单行文字编辑、删除、时间调整等操作。

[Windows] 视频字幕AI自动提取工具 青梧字幕 v0.9.13便携版

要说大家比较关心的就是支持单/双语字幕的下载和翻译，以满足诸位不同的使用需求。

[Windows] 视频字幕AI自动提取工具 青梧字幕 v0.9.13便携版

已开源：

对了，青梧字幕已在 Github 开源，所以是完全免费的，大家也可在本地自行编译，开源版本则完全剥离掉了登录认证的流程。

[Windows] 视频字幕AI自动提取工具 青梧字幕 v0.9.13便携版

到这里，软件的基础玩法已经为小伙伴介绍的差不多了，至于更加细节的玩法，就请大家下载后自己慢慢折腾吧。

提取码：HyHy


在线咨询
上一篇：链栈实现括号匹配检验
下一篇：Java 实现括号匹配：栈的应用与优化

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

推荐阅读
友情链接 浦江县 固阳县 杏花岭区 商都县 华坪县 那坡县 网站制作
Copyright © 2002-2019 雨点网络设计有限公司 版权所有   冀ICP备11025394号
联系电话：   E-mail：279303980@qq.com  
主营业务：技术文章网站建设、网站定制、技术文章营销型网站建设、技术文章网站优化、技术文章微商城制作、三级分销系统开发
电话沟通
在线客服