LeetCode20.Valid Parentheses(Easy)#Stack

 檢查一串括號是否為合法括號，而合法括號的要件是要左括號等於右括號的數量，並且要兩兩成對，且相同類型的括號要配相同類型的括號（譬如大括號要配大括號）。

如果是合法括號就回傳true，否則回傳false。

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

從左看到右，只要看到左括號，就把它放進Stack中，而當看到右括號，就看跟Stack最上方(stack.top())的左括號有沒有匹配，如果有的話，就表示目前還是合法的括號，繼續往下看，

而如果不匹配，代表現在的括號已經不合法，可以直接返回False了。

還有一種不合法情況是，先看到右括號但Stack是空的，那這樣也是不合法的，例如"](())"。

ans1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: bool isValid(string s) { set<char> st{'(','[','{'}; map<char,char> mp{{'(',')'} ,{'[',']'},{'{','}'}}; stack<char> stk; for(auto c:s){ if(st.find(c) != st.end()){ stk.push(c); }else{ if(stk.empty()) return false; char top = stk.top(); if(mp[top]==c){ stk.pop(); }else{ return false; } } } return stk.empty(); } };

ans2:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: bool isValid(string s) { stack<char> st; for (char c: s) { if (c == '(' || c == '{' || c == '[') { st.push(c); } else if (st.empty()) { return false; } else if (st.top() == '(' && c != ')') return false; else if (st.top() == '{' && c != '}') return false; else if (st.top() == '[' && c != ']') return false; else st.pop(); } return (st.empty()); } };

Ref:

https://www.algomooc.com/179.html

https://clay-atlas.com/blog/2021/01/22/leetcode-cn-20-valid-parentheses-solution/

https://www.catxcoder.com/easy/2022/02/11/20-Valid-Parentheses.html