利用C++栈结构实现括号匹配算法

在C++中，可以使用栈（stack）数据结构来实现括号匹配的功能。括号匹配是一个常见的问题，主要用来检查字符串中的括号是否正确配对（例如大括号与大括号 {}、小括号与小括号 ()、尖括号与尖括号 <> 等）。

下面是一个详细的代码示例和解释，展示了如何使用栈来实现括号匹配：

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>

using namespace std;

// 函数来检查括号是否匹配
bool isMatchingPair(char open, char close) {
    unordered_map<char, char> matchPairs = {
        {'(', ')'},
        {'{', '}'},
        {'<', '>'}
    };
    return matchPairs[open] == close;
}

// 函数来检查括号是否匹配
bool areBracketsBalanced(const string& expr) {
    stack<char> s;

    for (char ch : expr) {
        // 如果是左括号，压入栈
        if (ch == '(' || ch == '{' || ch == '<') {
            s.push(ch);
        }
        // 如果是右括号，检查栈顶元素是否匹配
        else if (ch == ')' || ch == '}' || ch == '>') {
            // 如果栈为空，说明没有对应的左括号
            if (s.empty()) {
                return false;
            }
            // 弹出栈顶元素并检查是否匹配
            char top = s.top();
            s.pop();
            if (!isMatchingPair(top, ch)) {
                return false;
            }
        }
    }

    // 最后检查栈是否为空，如果为空则所有括号都匹配
    return s.empty();
}

int main() {
    string expr;
    cout << "请输入一个包含括号的表达式: ";
    getline(cin, expr);

    if (areBracketsBalanced(expr)) {
        cout << "括号匹配成功！" << endl;
    } else {
        cout << "括号匹配失败！" << endl;
    }

    return 0;
}

代码详解

包含头文件：

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>

iostream 用于输入输出。

stack 用于存储括号。

string 用于处理字符串。

unordered_map 用于存储括号匹配对。

定义匹配函数：

bool isMatchingPair(char open, char close) {
    unordered_map<char, char> matchPairs = {
        {'(', ')'},
        {'{', '}'},
        {'<', '>'}
    };
    return matchPairs[open] == close;
}

使用一个哈希表 unordered_map 来存储左括号和右括号的匹配关系。

返回布尔值，表示两个括号是否匹配。

定义括号匹配函数：

bool areBracketsBalanced(const string& expr) {
    stack<char> s;

    for (char ch : expr) {
        if (ch == '(' || ch == '{' || ch == '<') {
            s.push(ch);
        } else if (ch == ')' || ch == '}' || ch == '>') {
            if (s.empty()) {
                return false;
            }
            char top = s.top();
            s.pop();
            if (!isMatchingPair(top, ch)) {
                return false;
            }
        }
    }

    return s.empty();
}

遍历字符串中的每个字符。
如果是左括号，则压入栈中。
如果是右括号，检查栈是否为空，如果为空则没有对应的左括号，返回 false。
否则，弹出栈顶元素并检查是否与当前右括号匹配，如果不匹配则返回 false。
最后检查栈是否为空，如果为空则所有括号都匹配，返回 true。
主函数：

int main() {
    string expr;
    cout << "请输入一个包含括号的表达式: ";
    getline(cin, expr);

    if (areBracketsBalanced(expr)) {
        cout << "括号匹配成功！" << endl;
    } else {
        cout << "括号匹配失败！" << endl;
    }

    return 0;
}