，

20. Valid Parentheses

這是一道堆疊的應用題，內容是有效的括號。

這題的要求是要判斷一個只包含括號字元 ( , ) , { , } , [ , ]的字串s是否為「有效」的。
一個字串要被判定為有效，必須滿足以下三個條件：

1.開閉類型必須匹配：每一個開啟的括號（open bracket）必須由相同類型的閉合括號（close bracket）來關閉。例如：( 必須由 ) 關閉；[ 必須由 ] 關閉；{ 必須由 } 關閉。

2.閉合順序必須正確：括號必須以正確的順序閉合。例如：( [ ] ) 是有效的，因為 [ 先開，後閉；( 後開，先閉。( [ ) ] 是無效的，因為 [ 應該在 ( 閉合之後才閉合。

3.每個閉合括號都有對應的開啟括號：每個閉合括號都必須找到一個未閉合的、相同類型的開啟括號與它匹配。

解決這類問題的最佳工具是堆疊（stack）。堆疊的後進先出（LIFO - Last In, First Out）特性，正好與括號的「後開先合」規則相符。
這題的核心思路是，當遇到開啟括號時：將他壓入堆疊（Push）。這代表遇到了一個正在等待閉合的括號，但遇到閉合括號時，這卻是需要進行判斷的時刻：首先先檢查堆疊是否為空：如果堆疊為空，表示沒有任何開啟括號在等待閉合，但出現了一個閉合括號，這顯然是無效的（例如 ]　），接著檢查類型是否匹配：如果堆疊不為空，取出堆疊最頂端的元素（Pop），它應該是與當前閉合括號類型匹配的開啟括號，如果匹配（例如遇到 )，堆疊頂是 ( ），則繼續處理下一個字元；如果不匹配（例如遇到 )，堆疊頂是 [ ），則字串無效。在遍歷結束後，如果處理完所有字元後，堆疊是空的，這表示所有開啟的括號都已找到對應的閉合括號並被清除，字串有效；如果堆疊非空，表示還有一些開啟括號沒有被閉合（例如 ({[ ），字串無效。