C++怎么實現驗證括號

這篇文章主要講解了“C++怎么實現驗證括號”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“C++怎么實現驗證括號”吧！

Valid Parentheses 驗證括號

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

這道題讓我們驗證輸入的字符串是否為括號字符串，包括大括號，中括號和小括號。這里需要用一個棧，開始遍歷輸入字符串，如果當前字符為左半邊括號時，則將其壓入棧中，如果遇到右半邊括號時，若此時棧為空，則直接返回 false，如不為空，則取出棧頂元素，若為對應的左半邊括號，則繼續循環，反之返回 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++怎么實現驗證括號”的內容了，經過本文的學習后，相信大家對C++怎么實現驗證括號這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！