《手撕資料結構經典題系列》有效括號問題

有效括號

力扣鏈接：20. 有效的括號 - 力扣（LeetCode） (leetcode-cn.com)

• 題目描述：

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串 s ，判斷字串是否有效，

• 有效字串需滿足：

左括號必須用相同型別的右括號閉合，
左括號必須以正確的順序閉合，

• 示例：

• 提示：

• 1 <= s.length <= 104
• s 僅由括號 '()[]{}' 組成

• 解題思路：

1. 這里我們使用堆疊來解決（先入后出的性質 ）
2. 在k題時首先得寫個堆疊出來
3. 讀取字符時如果遇到左括號則進行入堆疊操作
4. 如果遇到右括號則進行出堆疊操作，并對出堆疊資料與讀取資料進行匹配
5. 當匹配成功時，則繼續讀取字符
6. 當讀取結束并且堆疊中沒有資料則為有效字串，否則相反

• 圖示：

• 參考代碼：

bool isValid(char * s){
    //開辟堆疊
    ST st;
    StackInit(&st);
    char* str=s;
    while(*str!='\0')
    {
        
        //遇到左括號入堆疊
        if(*str=='('
        ||*str=='{'
        ||*str=='[')
        {
            StackPush(&st,*str);
            str++;
        }
        else
        {
            //遇到右括號出堆疊匹配
            if(*str=='}'
            ||*str==']'
            ||*str==')')
            {
                //為空堆疊時
                if(StackEmpty(&st))
                {
                    StackDestroy(&st);//注意堆疊空間銷毀（養成好的習慣）
                    return false;
                }
                else
                {
                    char tmp=StackTop(&st);//獲取堆疊頂資料
                    StackPop(&st);//出堆疊
                    if((*str==']'&&tmp!='[')
                    ||(*str=='}'&&tmp!='{')
                    ||(*str==')'&&tmp!='('))
                    {
                        //匹配失敗
                        StackDestroy(&st);
                        return false;
                    }
                    else
                        str++;
                }
            }
        }  
    }
    //遍歷完時堆疊還有資料為被出堆疊
    if(StackEmpty(&st))
    {
        StackDestroy(&st);//結束前先銷毀堆疊
        return true;
    }
    else
    {
        StackDestroy(&st);
        return false;
    }
}

• 附上堆疊原始碼：

//默認堆疊資料型別
typedef char STDataType;

//堆疊型別結構
typedef struct Stack
{
	//陣列堆疊（指向陣列的指標）
	STDataType* a;
	//堆疊頂位置
	int top;
	//堆疊容量
	int capacity;
}ST;

//堆疊初始化
void StackInit(ST* ps);
//堆疊銷毀
void StackDestroy(ST* ps);
//入堆疊
void StackPush(ST* ps, STDataType x);
//出堆疊
void StackPop(ST* ps);
//獲取堆疊頂資料
STDataType StackTop(ST* ps);
//堆疊使用空間大小
int StackSize(ST* ps);
//是否為空堆疊
bool StackEmpty(ST* ps);

//堆疊初始化
void StackInit(ST* ps)
{
	//避免傳入空指標
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//定義top為堆疊最后資料的后一個位置
	//也可以選擇讓top為當前最后資料的位置 此時初始化top=-1;
	ps->capacity = 0;
	return;
}
//堆疊銷毀
void StackDestroy(ST* ps)
{
	//避免傳入空指標
	assert(ps);
	free(ps->a);//釋放開辟的陣列堆疊空間
	ps->a = NULL;//置空，避免造成野指標
}
//入堆疊
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)//堆疊滿的情況
	{
		//如果原來容量為0則讓新容量為4，否則為兩倍
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//調整陣列堆疊大小（特別的：當陣列指標為NULL時，realloc的作用和malloc的作用一樣）
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(ST) * newcapacity);
		if (tmp == NULL)//tmp為NULL時則表示調整陣列空間失敗，那么就列印錯誤并結束行程
		{
			perror("realloc fail:");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;//存入資料
	ps->top++;//top位置更新
	return;
}
//出堆疊
void StackPop(ST* ps)
{
	//避免傳入空指標
	assert(ps);
	//出堆疊到資料個數為0結束
	if (StackEmpty(ps))
		return;
	ps->top--;//讓top減減得到出堆疊的效果
	return;
}
//獲取堆疊頂資料
STDataType StackTop(ST* ps)
{
	//避免傳入空指標
	assert(ps);
	//為空堆疊時無堆疊頂資料
	assert(!StackEmpty(ps));

	return ps->a[ps->top-1];//此時top-1才表示堆疊頂資料的下標
}
//堆疊使用空間大小
int StackSize(ST* ps)
{
	//避免傳入空指標
	assert(ps);

	return ps->top;
}
//是否為空堆疊
bool StackEmpty(ST* ps)
{
	//避免傳入空指標
	assert(ps);

	return ps->top == 0;
}

每日k題無煩惱，點贊學習不得了~