C++怎么實(shí)現(xiàn)驗(yàn)證括號(hào)

這篇文章主要講解了“C++怎么實(shí)現(xiàn)驗(yàn)證括號(hào)”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“C++怎么實(shí)現(xiàn)驗(yàn)證括號(hào)”吧！

Valid Parentheses 驗(yàn)證括號(hào)

Given a string containing just the characters "(", ")", "{", "}", "[" and "]", determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. 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

這道題讓我們驗(yàn)證輸入的字符串是否為括號(hào)字符串，包括大括號(hào)，中括號(hào)和小括號(hào)。這里需要用一個(gè)棧，開(kāi)始遍歷輸入字符串，如果當(dāng)前字符為左半邊括號(hào)時(shí)，則將其壓入棧中，如果遇到右半邊括號(hào)時(shí)，若此時(shí)棧為空，則直接返回 false，如不為空，則取出棧頂元素，若為對(duì)應(yīng)的左半邊括號(hào)，則繼續(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++怎么實(shí)現(xiàn)驗(yàn)證括號(hào)”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)C++怎么實(shí)現(xiàn)驗(yàn)證括號(hào)這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！