【04】C語言括號匹配問題

歡迎來到土土的博客~🥳🥳🌹🌹🌹
💥個人主頁：大耳朵土土垚的博客
💥 所屬專欄：C語言系列函數實現

題目描述：給定一個只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：

1.左括號必須用相同類型的右括號閉合。
2.左括號必須以正確的順序閉合。
3.每個右括號都有一個對應的相同類型的左括號。

也就是說第一個必須為左括號才可以匹配的上，一左一右，相鄰的同類型的左右括號可以消掉，最后能消完就行。跟消消樂一樣。

示例 1：

輸入：s = “()”
輸出：true
示例 2：

輸入：s = “()[]{}”
輸出：true
示例 3：

輸入：s = “{()}”
輸出：true
輸入：s = “{(})”
輸出：tfalse

解題思路：上篇博客我們學習了數據結構的棧和隊列——大耳朵土土的博客，這道題我們就可以根據棧的特點——后進先出來匹配括號，完成題解。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
// 支持動態增長的棧
typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;       // 棧頂int capacity;  // 容量 
}Stack;
// 初始化棧 
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;//指向棧頂的下一個數據//ps->top = -1; //則指向棧頂數據
}
// 檢測棧是否為空，如果為空返回true，如果不為空返回false
bool StackEmpty(Stack* ps)
{assert(ps);/*if (ps->top == 0)return true;elsereturn false;*/return ps->top == 0;
}
// 入棧 
void StackPush(Stack* ps, STDataType data)
{assert(ps);//STDataType tmp = ps->top == ps->capacity ? 4 : ps->capacity * 2;if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;ps->capacity = newcapacity;ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (ps->a == NULL){perror("realloc fail");return;}}ps->a[ps->top] = data;ps->top++;}
// 出棧 
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));//判斷非空ps->top--;
}
// 獲取棧頂元素 
STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));//判斷非空return ps->a[ps->top - 1];}
// 獲取棧中有效元素個數 
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}// 銷毀棧 
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->capacity = 0;ps->a = NULL;ps->top = 0;
}
//上面是C語言棧的實現，注意這里將int類型改為了char類型，利用typedef很容易全部改正

下面我們將通過上面的棧來解題


bool isValid(char* s) {Stack st;StackInit(&st);while (*s){if (*s == '(' || *s == '[' || *s == '{')//左括號{StackPush(&st, *s);}else//右括號{   if(StackEmpty(&st)){StackDestroy(&st);return false;}char top = StackTop(&st);StackPop(&st);if ((*s == ')' && top != '(')||(*s == ']' && top != '[')||(*s == '}' && top != '{'))//判斷是否與上一個元素匹配{StackDestroy(&st);return false;}}s++;}bool ret = StackEmpty(&st);StackDestroy(&st);//記得釋放空間return ret;
}