c++中如何使用stack实现括号匹配_c++ stack括号匹配方法-C++-PHP中文网

c++中如何使用stack实现括号匹配_c++ stack括号匹配方法

裘德小鎮的故事

发布： 2025-09-27 17:08:02

原创

433人浏览过

使用stack容器实现括号匹配，遍历字符串，左括号入栈，右括号与栈顶匹配则出栈，否则失败，最终栈空为成功。

c++中如何使用stack实现括号匹配_c++ stack括号匹配方法

在C++中，可以利用stack容器来高效地实现括号匹配问题。核心思想是：遇到左括号时入栈，遇到右括号时检查栈顶是否为对应的左括号，若是则出栈，否则匹配失败。最终栈应为空，表示所有括号都正确匹配。

1. 包含必要头文件并使用命名空间

使用stack需要包含#include <stack>，同时常用using namespace std;简化代码。

#include <iostream>
#include <stack>
#include <string>
using namespace std;

登录后复制

2. 实现括号匹配函数

定义一个函数bool isValid(string s)，遍历字符串中的每个字符：

如果是左括号 '('、'{' 或 '['，将其压入栈中。
如果是右括号，则检查栈是否为空或栈顶不匹配，若成立则返回false；否则弹出栈顶元素。
遍历结束后，栈为空说明匹配成功。

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        }
        else {
            if (st.empty()) return false;
            if (c == ')' && st.top() != '(') return false;
            if (c == '}' && st.top() != '{') return false;
            if (c == ']' && st.top() != '[') return false;
            st.pop();
        }
    }
    return st.empty();
}

登录后复制

3. 主函数测试示例

调用函数并输出结果，验证不同输入情况。

琅琅配音

全能AI配音神器

208

查看详情

立即学习“C++免费学习笔记（深入）”；

int main() {
    string expr = "{[()]}";
    if (isValid(expr))
        cout << "括号匹配正确" << endl;
    else
        cout << "括号匹配错误" << endl;
    return 0;
}

登录后复制

该方法时间复杂度为O(n)，空间复杂度最坏为O(n)。适用于判断表达式中圆括号、花括号和方括号的嵌套与顺序是否合法。

基本上就这些。

以上就是c++++中如何使用stack实现括号匹配_c++ stack括号匹配方法的详细内容，更多请关注php中文网其它相关文章！