帶你一步實現(xiàn)《棧》（括號匹配問題）

棧的結(jié)構(gòu)及概念

棧是一種特殊的線性表，只允許在固定的一端插入或刪除數(shù)據(jù)，進行插入和刪除的一端被稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)遵循后進先出原則

LIFO（LAST IN FIRST OUT)

一步一步來實現(xiàn)他

//靜態(tài)的
//#define N 10
//struct stack
//{
//	int  a[N];
//	int top;
//};
typedef int TYPE;
typedef struct Stack
{
	TYPE* a; 	
	TYPE top;
	int capacity;
}ST;

如果還是用靜態(tài)的數(shù)組就太低端了，而且還會遇到容量不夠的問題,因為要儲存的值的類型有可能會發(fā)生變化，所以可以將變量類型定義一下，需要修改時不至于要修改很多地方。

進入正題

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

判斷創(chuàng)建的結(jié)構(gòu)體指針變量是否為空assert

將ps指向的數(shù)組先置空，然后將容量設(shè)置為0，數(shù)據(jù)量設(shè)置為0。

判空函數(shù)

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

還是要檢查ps是否有問題，返回一個bool變量，判斷是false還是true，如果等于0，就返回true，說明棧內(nèi)為空。

求棧內(nèi)元素個數(shù)

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

這個很簡單，只需要返回top的值即可。

刪除元素

這個很很簡單相較于用鏈表實現(xiàn)

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

即可，當然如果ps指向的top已經(jīng)是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;
}

判斷必不可少，因為內(nèi)存是malloc過來的，要用free函數(shù)將其釋放掉，然后恢復(fù)到初始化函數(shù)時的狀態(tài)。將容量還有數(shù)量全部還原為零。

獲取棧頂元素

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

判斷棧內(nèi)到底有沒有元素，這是很重要的，不然會越界訪問，然后返回入棧的數(shù)量減一下標的元素即可，為什么減一呢，第一個元素，下標為零，懂了吧！

別忘記在STACK.h中聲明這幾個函數(shù)

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;
}

學習完了棧的定義及實現(xiàn)，上一個重頭戲

題目：括號的匹配

在這里插入圖片描述

這道題實現(xiàn)起來很不簡單，如果沒有學習棧相關(guān)的知識，我們在判斷時會遇到很多阻力，這道題也可以叫做括號的匹配。例如

分析題目要求，仔細分析可以發(fā)現(xiàn)，在利用括號開始進行匹配時，如果是右括號（統(tǒng)稱）那就入棧，如果是左括號，那就從棧中取出一個元素與其相匹配，如果匹配成功，那就繼續(xù)向后匹配，如果匹配失敗，那就直接返回，并標明匹配錯誤。

拿出一個測試用例進行解釋

在這里插入圖片描述

接下來解決邏輯問題

首先，因為我們需要用到棧，可以將上邊所講的棧的實現(xiàn)函數(shù)全部復(fù)制粘貼進去，然后利用棧的特性來實現(xiàn)大體邏輯。

代碼如下

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;
}

創(chuàng)建一個結(jié)構(gòu)體指針變量，這里要注意，上邊所寫的默認是整型數(shù)組，將設(shè)置的TYPE改成char類型即可。

在循環(huán)體中，我們可以選擇使用switch case語句，也可以用if else 語句，代碼邏輯十分清晰，在遍歷數(shù)組的過程中，如果是右括號，則直接入棧，如果是左括號，就出棧頂元素與其相匹配，匹配成功，則走到循環(huán)體最后s++的位置，進行下一次判斷。

也要注意數(shù)組是否為空，可以使用判空函數(shù)，如果為空就返回true，如果不為空就返回false，如果是空的話，相當于經(jīng)歷循環(huán)體后已經(jīng)沒有左括號了，但是如果不為空的話，那就相當于數(shù)組中還剩下一些括號，這些括號是沒有被匹配的。

例如

{}()[]{{{

經(jīng)歷過循環(huán)后，前邊的三組已經(jīng)匹配完成了，然而后邊還有三個右括號入棧，這三個括號沒有匹配，所以用判空函數(shù)判斷一下，如果循環(huán)之后棧不為空的話，那就說明匹配不成功，返回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便攜版

哈嘍，黑域小伙伴，現(xiàn)在很多同學和 up 主都會拍一些 Vlog 或轉(zhuǎn)載各種各樣的視頻傳到網(wǎng)上分享，然而工作量比較大且較為枯燥的就是給視頻加字幕了，而依靠人工去聽寫制作字幕效率真的很慢。所以說在當今數(shù)字化時代，字幕提取通常是影視制作和字幕翻譯過程中的重要環(huán)節(jié)。

但是直接從視頻里面提取出硬字幕可不是件容易的事，一兩分鐘的短視頻還好，自己還可以想些辦法（如錄音轉(zhuǎn)文字）輕松提取文案。盡管現(xiàn)在市面上已經(jīng)有許多類似的字幕軟件或商家提供在線服務(wù)，但它們往往收費、限制了提取時長，要么各種套路，實在沒意思。

所以這次，我就給大家安利一款跨平臺超好用的AI視頻字幕智能提取翻譯工具，有了這款神器，一鍵提取視頻中你想要的各種文字！

具體我們來打開體驗下：

青梧字幕是一款基于 Whisper 的AI字幕提取工具，它通過先進的AI算法和高效的字幕提取技術(shù)，能夠自動從視頻文件中提取字幕內(nèi)容。

目前暫支持 Windows 及 Mac（M及intel系列處理器）系統(tǒng)環(huán)境，支持識別中、英、日、韓等99種語言，支持srt/vtt/lrc等常見字幕格式。

[Windows] 視頻字幕AI自動提取工具青梧字幕 v0.9.13便攜版