您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“C++實現(xiàn)驗證括號的方法”的有關(guān)知識,在實際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
這道題讓我們驗證輸入的字符串是否為括號字符串,包括大括號,中括號和小括號。這里需要用一個棧,開始遍歷輸入字符串,如果當(dāng)前字符為左半邊括號時,則將其壓入棧中,如果遇到右半邊括號時,若此時棧為空,則直接返回 false,如不為空,則取出棧頂元素,若為對應(yīng)的左半邊括號,則繼續(xù)循環(huán),反之返回 false,代碼如下:
方法一:
class Solution { public: bool isValid(string s) { stack<char> parentheses; for (int i = 0; i < s.size(); ++i) { if (s[i] == '(' || s[i] == '[' || s[i] == '{') parentheses.push(s[i]); else { if (parentheses.empty()) return false; if (s[i] == ')' && parentheses.top() != '(') return false; if (s[i] == ']' && parentheses.top() != '[') return false; if (s[i] == '}' && parentheses.top() != '{') return false; parentheses.pop(); } } return parentheses.empty(); } };
方法二:
class Solution { public: bool isValid(string s) { int n = s.size(); if (n % 2 == 1) { return false; } unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} }; stack<char> stk; for (char ch: s) { if (pairs.count(ch)) { if (stk.empty() || stk.top() != pairs[ch]) { return false; } stk.pop(); } else { stk.push(ch); } } return stk.empty(); } };
“C++實現(xiàn)驗證括號的方法”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。