20. 有效的括號 - 力扣（LeetCode）
https://leetcode.cn/problems/valid-parentheses/
題目
給定一個只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效。
有效字符串需滿足：
- 左括號必須用相同類型的右括號閉合。
- 左括號必須以正確的順序閉合。
- 每個右括號都有一個對應的相同類型的左括號。
示例 1：
輸入：s = "()" 輸出：true
示例?2：
輸入：s = "()[]{}"
輸出：true
示例?3：
輸入：s = "(]" 輸出：false
提示：
1 <= s.length <= 104s?僅由括號?'()[]{}'?組成
圖解
代碼(思路都在代碼中)
typedef char STDataType;
// 棧的結構
typedef struct Stack {STDataType* a; // 指針int top; // 棧頂int capacity; // 容量
} Stack;
// 擴容函數
void Exp(Stack* p) {if (p->capacity == p->top) {// 利用三目運算來判斷是否int New_cap = p->capacity == 0 ? 4 : p->capacity * 2;STDataType* tmp =(STDataType*)realloc(p->a, New_cap * sizeof(STDataType));if (tmp == NULL) {assert("realloc");return;}// 將開辟空間給給原來的變量p->a = tmp;p->capacity = New_cap;}
}// 初始化
void StackInit(Stack* p) {assert(p);p->a = NULL;p->capacity = p->top = 0;
}
// 入棧
void StackPush(Stack* p, STDataType data) {assert(p);// 判斷空間Exp(p);// 入棧p->a[p->top] = data;// 入棧后棧頂向上移動p->top++;
}
// 出棧
void StackPop(Stack* p) {assert(p);assert(p->top > 0); // 確保不為空// 判斷是否元素是否為0,避免越界/*if (p->top == 0){return;}*/p->top--;
}
// 獲取棧頂元素
STDataType StackTop(Stack* p) {// 判斷是否為0if (p->top == 0) {return (STDataType)0; // 由于返回類型是 STDataType，所以需要強制轉換}return p->a[p->top - 1];
}
// 獲取棧中有效元素個數
int StackSize(Stack* p) { return p->top; }
// 判空
bool StackEmpty(Stack* p) {// 使用邏輯非操作符(!)來檢查棧頂指針(top)是否為0（即棧是否為空）// 如果top為0，說明棧中沒有任何元素，因此棧是空的// 在C語言中，邏輯非操作符會將0轉換為1（true），非0轉換為0（false）// 所以當棧頂指針top為0時，!p->top的結果為true（非零值），表示棧為空// 反之，如果棧中有元素（top非0），則!p->top的結果為false（0），表示棧非空return !p->top;
}
// 銷毀棧
void StackDestroy(Stack* p) {if (p->a) {free(p->a);p->a = NULL;p->capacity = p->top = 0;}
}
bool isValid(char* s) {// 思路：我們利用棧來解決這個問題，利用進先出的特性// 創建棧Stack s1;// 初始化棧StackInit(&s1);// 利用循環來遍歷字符while (*s) {// 讓左括號入棧if (*s == '(' || *s == '{' || *s == '[' ) {StackPush(&s1, *s);} else { // 右括號取棧頂的左括號匹配// 首先我們判斷是否為空if (StackEmpty(&s1)) { // 這里說明棧我為空(也就是說左括號沒有和右括號對應或者說就只有一個右括號)StackDestroy(&s1); // 直接釋放棧return false;}// 獲取棧頂元素(這里就有了后進先出的原理了)STDataType top = StackTop(&s1);// 獲取后出棧，方便下一次入棧StackPop(&s1);// 判斷是否對應(這邊判斷的條件是不相等，這樣就可以排除所有可能false)if ((top == '{' && *s != '}')||(top == '[' && *s != ']')||(top == '(' && *s != ')'))// 也就是說：棧里面的左括號&&字符中不等于和他對應的右括號{return false;StackDestroy(&s1);}}++s; // 每次遍歷向后移動}// 循環跳出就意味著排除了這些可能，但是這邊我們不排除只有一個左括號或者右括號或者左括號比右括號多，所以需要判空bool ret = StackEmpty(&s1);StackDestroy(&s1); // 這邊我們需要釋放一下，避免空間泄露return ret;
}
)
