# 20. Valid Parentheses

### Backgroud
problem: https://leetcode.com/problems/valid-parentheses/
寫個程式驗證一個包含各排列的大中小括號的字串是符合條件的。
如果符合條件return True 不然就 Return False

### Code

class Solution:
    def isValid(self, s: str) -> bool:
        ## 雖然題目中有說明不會出現空值，但這一步先定義空值為False
        if s == "":
            return False
            
        ## 定義一個空list
        l = []
        
        ## 開始遍歷整個string並逐一比對
        for i in s:
            ## 遇到對應的起始括號，'('，'['或'{'就塞一個對應的結束括號到list中
            if i == "[":
                l.append("]")
            elif i == "(":
                l.append(")")
            elif i == "{":
                l.append("}")
            
            ## 1.判斷list是否為空，是空（not bool(l))的話代表這
            ##     是一個與沒有成對起始括號的結束括號，
            ##     因為1. 前面沒有塞東西進去或2.都被pop完了。
            ## 2. 將列表中最後存進的取出並判斷是否與目前遇到的一致，
            ##     如果不是的話代表此結束括號前端正確的位置沒有對應的起始括號
            else:
               if not bool(l) or i != l.pop():
                   return False
        ## 判斷最後list中是否有未盡的結束括號，
        ##     空的話代表遍歷完成並且全部括號按照先開後關規則成對，
        ##     反之代表輸入中有起始符號未關閉。
        return not bool(l)

### Explantion
這題使用堆疊(Stack)的先進後出，後進先出的紀錄方式來記錄括號的先開後關，後開先關。在python中我們利用list的append()與pop()來做。
請直接往上看code或看圖解。
關於堆疊的[解釋](https://zh.wikipedia.org/zh-tw/%E5%A0%86%E6%A0%88)


###### tags: `leetcode` `easy` `stack`