題目描述

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

• 有效字符串需滿足：
• 左括號(hào)必須用相同類型的右括號(hào)閉合。
• 左括號(hào)必須以正確的順序閉合。
• 每個(gè)右括號(hào)都有一個(gè)對(duì)應(yīng)的相同類型的左括號(hào)
  測(cè)試樣例1：

輸入：s = "()"
輸出：true

測(cè)試樣例2：

輸入：s = "(]"
輸出：false

測(cè)試樣例3：

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

思路

本題考察棧的應(yīng)用。這里使用stl實(shí)現(xiàn)。
要考慮以下幾種情況：
/*******
1.前面括號(hào)全都匹配成功，此時(shí)棧空了，但下一個(gè)元素是右括號(hào)。例如(())｝
2.左括括號(hào)入棧后，只有但左括號(hào)，后面的全部匹配。此時(shí)，棧遍歷一遍棧不為空。例如：{()()

3、左括號(hào)入棧后，來一個(gè)非匹配的有括號(hào)：{(}

原則：遇到左括號(hào)就入棧，遇到右的括號(hào)就取棧頂一個(gè)元素出棧來消耗一個(gè)右括號(hào)

注意：本題用了stl，pop()無返回值，如果有返回值代碼更簡(jiǎn)潔，當(dāng)然也可以使用別的方法。我這里僅僅提供一種思路。

class Solution {
public:bool isValid(string s) {stack<char> st;//定義一個(gè)棧for(int i=0;i<s.size();i++){if(s[i]=='(' || s[i]=='{' || s[i]=='['){//當(dāng)是左括號(hào)時(shí)入棧。st.push(s[i]);//壓入棧中}else{//右括號(hào)if(st.empty()==true)//是右括號(hào)但是棧中已空，（屬于上面的第一種情況）return false;//匹配失敗if(s[i]==')' && st.top()!='('){ //如果掃描到的是右括號(hào)，從棧中彈出的，也就是消耗出來的不與之匹配（屬于第三種情況）return false;//匹配失敗}else if(s[i]==')' && st.top()=='('){//如果左右匹配，則彈出元素。st.pop();}if(s[i]=='}' && st.top()!='{'){ //同上return false;//匹配失敗}else if(s[i]=='}' && st.top()=='{'){st.pop();}if(s[i]==']' && st.top()!='['){ //同上return false;//匹配失敗}else if(s[i]==']' && st.top()=='['){st.pop();}}}
//循環(huán)遍歷一遍后，如果棧最后為空，則匹配成功if(st.empty()){return true;}else{return false;}//棧中不空，屬于第二種情況，代表有單左括號(hào)。}
};

但還有一些技巧，在匹配左括號(hào)的時(shí)候，右括號(hào)先入棧，就只需要比較當(dāng)前元素和棧頂相不相等就可以了，比左括號(hào)先入棧代碼實(shí)現(xiàn)要簡(jiǎn)單的多了！

方法二：

class Solution {
public:bool isValid(string s) {if (s.size() % 2 != 0) return false; // 如果s的長(zhǎng)度為奇數(shù)，一定不符合要求stack<char> st;for (int i = 0; i < s.size(); i++) {if (s[i] == '(') st.push(')');else if (s[i] == '{') st.push('}');else if (s[i] == '[') st.push(']');// 第三種情況：遍歷字符串匹配的過程中，棧已經(jīng)為空了，沒有匹配的字符了，說明右括號(hào)沒有找到對(duì)應(yīng)的左括號(hào) return false// 第二種情況：遍歷字符串匹配的過程中，發(fā)現(xiàn)棧里沒有我們要匹配的字符。所以return falseelse if (st.empty() || st.top() != s[i]) return false;else st.pop(); // st.top() 與 s[i]相等，棧彈出元素}// 第一種情況：此時(shí)我們已經(jīng)遍歷完了字符串，但是棧不為空，說明有相應(yīng)的左括號(hào)沒有右括號(hào)來匹配，所以return false，否則就return truereturn st.empty();}
};