題目鏈接：20.有效的括號

題目描述：

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

有效字符串需滿足：

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

示例 1：

輸入：s = "()"

輸出：true

示例 2：

輸入：s = "()[]{}"

輸出：true

示例 3：

輸入：s = "(]"

輸出：false

示例 4：

輸入：s = "([])"

輸出：true

提示：

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

思路：借助數據結構棧，左括號入棧，右括號匹配?

? ? ? ? 由于棧的先進后出的特性，可以借助棧來實現對應括號的消除，匹配。

? ? ? ? 使用棧之前需要添加實現棧的相關代碼：參考棧：數據結構中的“時間管理大師”? ? ? ??

    char* ps = s;Stack st;StackInit(&st);

? ? ? ? 定義指針ps指向給定字符串，用來遍歷括號，創建棧st并初始化。

????????以示例2為例：

????????若當前遍歷到左括號：? ? ? ?

        if (*ps == '(' || *ps == '[' || *ps == '{'){StackPush(&st,*ps);}

·? ? ? ? 直接讓左括號入棧。?

? ? ? ? ?若當前遍歷到右括號，需要考慮兩種情況：

            if (StackEmpty(&st)){StackDestroy(&st);return false;}

? ? ? ? 若當前棧為空，s為圖示字符串，那么直接銷毀棧，返回false。

int top = StackTop(&st);
if ((*ps == ')' && top != '(') || (*ps == ']' && top != '[') || (*ps == '}' && top != '{'))
{StackDestroy(&st);return false;
}
StackPop(&st);

? ? ? ? 若當前棧不為空，取棧頂元素與右括號進行匹配：

????????????????若合法，將棧頂元素出棧，進行下一組括號的匹配。

????????????????若不合法，銷毀棧并返回false。? ? ? ?

? ? ? ? 若s為圖中所示字符串，在匹配完合法括號后還有左括號入棧，那么就會導致跳出循環后棧不為空，所以需要對循環后的棧進行判空，這里使用三目操作符：

    bool ret = StackEmpty(&st) ? true : false;StackDestroy(&st);return ret;

? ? ? ? 若當前棧為空，返回true，若當前棧不為空，說明棧中還有左括號，返回false，保存返回值后銷毀鏈表，返回ret即可。?

完整代碼：

typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top;		// 棧頂int _capacity;  // 容量 
}Stack;// 初始化棧 
void StackInit(Stack* ps)
{ps->_a = NULL;ps->_top = ps->_capacity = 0;
}// 入棧 
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->_top == ps->_capacity){int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc");exit(1);}ps->_a = tmp;ps->_capacity = newcapacity;}ps->_a[ps->_top++] = data;
}// 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0 
int StackEmpty(Stack* ps)
{assert(ps);return ps->_top == 0;
}// 出棧 
void StackPop(Stack* ps) 
{assert(!StackEmpty(ps));--ps->_top;
}// 獲取棧頂元素 
STDataType StackTop(Stack* ps)
{assert(!StackEmpty(ps));return ps->_a[ps->_top - 1];
}// 獲取棧中有效元素個數 
int StackSize(Stack* ps)
{assert(ps);return ps->_top;
}// 銷毀棧 
void StackDestroy(Stack* ps)
{if (ps->_a)ps->_a = NULL;ps->_top = ps->_capacity = 0;
}bool isValid(char* s) {char* ps = s;Stack st;StackInit(&st);while(*ps != '\0'){if (*ps == '(' || *ps == '[' || *ps == '{'){StackPush(&st,*ps);}else{if (StackEmpty(&st)){StackDestroy(&st);return false;}int top = StackTop(&st);if ((*ps == ')' && top != '(') || (*ps == ']' && top != '[') || (*ps == '}' && top != '{')){StackDestroy(&st);return false;}StackPop(&st);}ps++;}bool ret = StackEmpty(&st) ? true : false;StackDestroy(&st);return ret;
}

?