題目
給定一個(gè)只包括 '('哈扮，')'，'{'蚓再，'}'滑肉，'['，']' 的字符串摘仅，判斷字符串是否有效靶庙。
有效字符串需滿足：
- 左括號(hào)必須用相同類型的右括號(hào)閉合。
- 左括號(hào)必須以正確的順序閉合娃属。
注意空字符串可被認(rèn)為是有效字符串六荒。
示例1：
輸入:"()"
輸出: true
示例2：
輸入:"()[]{}"
輸出: true
示例3：
輸入:"(]"
輸出: false
示例4：
輸入:"([)]"
輸出: false
示例5：
輸入:"{[]}"
輸出: true
思路
1.一個(gè)簡(jiǎn)單的例子：
如果只有一類符號(hào)的該類問(wèn)題，即假設(shè)檢測(cè)'()'是否是有效字符矾端，則可以通過(guò)計(jì)數(shù)的方法去判斷掏击，當(dāng)遇到'('時(shí)總數(shù)加1，遇到')'時(shí)總數(shù)減1秩铆。在遍歷字符串的過(guò)程中砚亭，只要出現(xiàn)總數(shù)小于0的情況就是無(wú)效字符串灯变，以及遍歷完成后總數(shù)是否為0來(lái)判斷字符串是否有效。但是此方法對(duì)于多種類型的符號(hào)捅膘，就不再適合添祸。
2.使用棧數(shù)據(jù)結(jié)構(gòu)：
使用棧數(shù)據(jù)結(jié)構(gòu)，遍歷字符串每個(gè)符號(hào)寻仗，遇見(jiàn)開括號(hào)刃泌，就將其推到棧上，當(dāng)遇到閉括號(hào)署尤，就檢查棧頂?shù)脑匕姨妫绻麠ｍ斒且粋€(gè)相同類型的左括號(hào)，我們就將其從棧中彈出沐寺。否則林艘，即為無(wú)效的字符串。如果遍歷完混坞，棧中仍然有元素狐援，這也意味著表達(dá)式無(wú)效。
解答
class Solution {
public:
bool isValid(string s) {
if (s.size() % 2)
return false;
stack<char> sta;
char top;
for (auto x : s) {
//右括號(hào)究孕，推入棧
if (x == '(' || x == '[' || x == '{') {
sta.push(x);
continue;
}
//遇見(jiàn)左括號(hào)啥酱，但是棧中沒(méi)有元素
else if (sta.empty()) return false;
//如果當(dāng)前元素與棧頂元素匹配，彈出
top = sta.top();
if ((x == ')' && top == '(') ||
(x == ']' && top == '[') ||
(x == '}' && top == '{'))
{
sta.pop();
}
else return false;
}
//最后厨诸，如果棧為空镶殷，則是有效括號(hào)
if (sta.empty())
return true;
else
return false;
}
};
【關(guān)注公眾號(hào)DoCode，每日一道LeetCode微酬，將零碎時(shí)間利用起來(lái)】
