讀完本文，你不僅學會了演算法套路，還可以順便去 LeetCode 上拿下如下題目：
20.有效的括號
921.使括號有效的最小插入
1541.平衡括號串的最少插入
-----------
判斷合法括號串對括號的合法性判斷多次在筆試中出現，現實中也很常見，比如說我們寫的程式碼，編輯器會檢查括號是否正確閉合。而且我們的程式碼可能會包含三種括號 [](){}，判斷起來有一點難度。
來看一看力扣第 20 題「有效的括號」，輸入一個字串，其中包含 [](){} 六種括號，請你判斷這個字串組成的括號是否合法。
舉幾個例子：
Input: "()[]{}"Output: trueInput: "([)]"Output: falseInput: "{[]}"Output: true解決這個問題之前，我們先降低難度，思考一下，如果只有一種括號 ()，應該如何判斷字串組成的括號是否合法呢？
假設字串中只有圓括號，如果想讓括號字串合法，那麼必須做到：
每個右括號 ) 的左邊必須有一個左括號 ( 和它匹配。
比如說字串 ()))(( 中，中間的兩個右括號左邊就沒有左括號匹配，所以這個括號組合是不合法的。
那麼根據這個思路，我們可以寫出演算法：
bool isValid(string str) { // 待匹配的左括號數量 int left = 0; for (int i = 0; i < str.size(); i++) { if (s[i] == '(') { left++; } else { // 遇到右括號 left--; } // 右括號太多 if (left == -1) return false; } // 是否所有的左括號都被匹配了 return left == 0;}如果只有圓括號，這樣就能正確判斷合法性。對於三種括號的情況，我一開始想模仿這個思路，定義三個變數 left1，left2，left3 分別處理每種括號，雖然要多寫不少 if else 分支，但是似乎可以解決問題。
但實際上直接照搬這種思路是不行的，比如說只有一個括號的情況下 (()) 是合法的，但是多種括號的情況下， [(]) 顯然是不合法的。
僅僅記錄每種左括號出現的次數已經不能做出正確判斷了，我們要加大儲存的資訊量，可以利用棧來模仿類似的思路。棧是一種先進後出的資料結構，處理括號問題的時候尤其有用。
我們這道題就用一個名為 left 的棧代替之前思路中的 left 變數，遇到左括號就入棧，遇到右括號就去棧中尋找最近的左括號，看是否匹配：
bool isValid(string str) { stack<char> left; for (char c : str) { if (c == '(' || c == '{' || c == '[') left.push(c); else { // 字元 c 是右括號 if (!left.empty() && leftOf(c) == left.top()) left.pop(); else // 和最近的左括號不匹配 return false; } } // 是否所有的左括號都被匹配了 return left.empty();}char leftOf(char c) { if (c == '}') return '{'; if (c == ')') return '('; return '[';}接下來講另外兩個常見的問題，如何透過最小的插入次數將括號變成合法的？
平衡括號串（一）先來個簡單的，力扣第 921 題「使括號有效的最少新增」：
給你輸入一個字串 s，你可以在其中的任意位置插入左括號 ( 或者右括號 )，請問你最少需要幾次插入才能使得 s 變成一個合法的括號串？
比如說輸入 s = "())("，演算法應該返回 2，因為我們至少需要插入兩次把 s 變成 "(())()"，這樣每個左括號都有一個右括號匹配，s 是一個合法的括號串。
這其實和前文的判斷括號合法性非常類似，我們直接看程式碼：
int minAddToMakeValid(string s) { // res 記錄插入次數 int res = 0; // need 變數記錄右括號的需求量 int need = 0; for (int i = 0; i < s.size(); i++) { if (s[i] == '(') { // 對右括號的需求 + 1 need++; } if (s[i] == ')') { // 對右括號的需求 - 1 need--; if (need == -1) { need = 0; // 需插入一個左括號 res++; } } } return res + need;}這段程式碼就是最終解法，核心思路是以左括號為基準，透過維護對右括號的需求數 need，來計算最小的插入次數。需要注意兩個地方：
1、當 need == -1 的時候意味著什麼？
因為只有遇到右括號 ) 的時候才會 need--，need == -1 意味著右括號太多了，所以需要插入左括號。
比如說 s = "))" 這種情況，需要插入 2 個左括號，使得 s 變成 "()()"，才是一個合法括號串。
2、演算法為什麼返回 res + need？
因為 res 記錄的左括號的插入次數，need 記錄了右括號的需求，當 for 迴圈結束後，若 need 不為 0，那麼就意味著右括號還不夠，需要插入。
比如說 s = "))(" 這種情況，插入 2 個左括號之後，還要再插入 1 個右括號，使得 s 變成 "()()()"，才是一個合法括號串。
以上就是這道題的思路，接下來我們看一道進階題目，如果左右括號不是 1:1 配對，會出現什麼問題呢？
平衡括號串（二）這是力扣第 1541 題「平衡括號字串的最少插入次數」：
現在假設 1 個左括號需要匹配 2 個右括號才叫做合法的括號組合，那麼給你輸入一個括號串 s，請問你如何計算使得 s 合法的最小插入次數呢？
核心思路還是和剛才一樣，透過一個 need 變數記錄對右括號的需求數，根據 need 的變化來判斷是否需要插入。
第一步，我們按照剛才的思路正確維護 need 變數：
int minInsertions(string s) { // need 記錄需右括號的需求量 int res = 0, need = 0; for (int i = 0; i < s.size(); i++) { // 一個左括號對應兩個右括號 if (s[i] == '(') { need += 2; } if (s[i] == ')') { need--; } } return res + need;}現在想一想，當 need 為什麼值的時候，我們可以確定需要進行插入？
首先，類似第一題，當 need == -1 時，意味著我們遇到一個多餘的右括號，顯然需要插入一個左括號。
比如說當 s = ")"，我們肯定需要插入一個左括號讓 s = "()"，但是由於一個左括號需要兩個右括號，所以對右括號的需求量變為 1：
if (s[i] == ')') { need--; // 說明右括號太多了 if (need == -1) { // 需要插入一個左括號 res++; // 同時，對右括號的需求變為 1 need = 1; }}另外，當遇到左括號時，若對右括號的需求量為奇數，需要插入 1 個右括號。因為一個左括號需要兩個右括號嘛，右括號的需求必須是偶數，這一點也是本題的難點。
所以遇到左括號時要做如下判斷：
if (s[i] == '(') { need += 2; if (need % 2 == 1) { // 插入一個右括號 res++; // 對右括號的需求減一 need--; }}綜上，我們可以寫出正確的程式碼：
int minInsertions(string s) { int res = 0, need = 0; for (int i = 0; i < s.size(); i++) { if (s[i] == '(') { need += 2; if (need % 2 == 1) { res++; need--; } } if (s[i] == ')') { need--; if (need == -1) { res++; need = 1; } } } return res + need;}綜上，三道括號相關的問題就解決了，其實我們前文 合法括號生成演算法 也是括號相關的問題，但是使用的回溯演算法技巧，和本文的幾道題差別還是蠻大的，有興趣的讀者可以去看看。