括号匹配问题c++示例代码

在C++中，括号匹配问题是一个经典的计算机科学问题，通常用于检查字符串中的括号是否有效配对。例如，判断`()"[]{}()`这样的括号序列是否可以形成有效的嵌套。下面是一个简单的递归回溯算法的C++示例：

#include <iostream>
#include <string>

bool isValid(std::string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') { // 入栈非空元素
            st.push(c);
        } else if (!st.empty() && (c == ')' && st.top() == '(' ||
                                  c == '}' && st.top() == '{' ||
                                  c == ']' && st.top() == '[')) { // 匹配规则检查
            st.pop();
        } else {
            return false; // 遇到非法字符，立即返回false
        }
    }

    // 如果所有的左括号都有对应的右括号，且栈为空，则说明有效
    return st.empty();
}

int main() {
    std::string testCases[] = {"()", "({})", "([)]", "({[()()]})"};
    for (const auto& str : testCases) {
        if (isValid(str)) {
            std::cout << str << " is valid.\n";
        } else {
            std::cout << str << " is not valid.\n";
        }
    }
    return 0;
}

这个程序定义了一个函数`isValid`，它接受一个包含括号的字符串，通过遍历并使用栈的数据结构来检查括号是否有效匹配。如果最后栈为空，表示所有括号都已正确关闭。