C++括号匹配算法：使用栈实现

这篇文章介绍如何使用C++中的栈来实现一个简单的括号匹配算法。该算法可以检查包含三种括号的表达式是否平衡：圆括号 ()，方括号 [] 和花括号 {}。

代码实现cpp#include #include #include

bool isMatching(char opening, char closing) { if (opening == '(' && closing == ')') return true; else if (opening == '[' && closing == ']') return true; else if (opening == '{' && closing == '}') return true; else return false;}

bool isBalanced(const std::string& sequence) { std::stack brackets; for (char bracket : sequence) { if (bracket == '(' || bracket == '[' || bracket == '{') { brackets.push(bracket); } else if (bracket == ')' || bracket == ']' || bracket == '}') { if (brackets.empty() || !isMatching(brackets.top(), bracket)) { return false; } else { brackets.pop(); } } } return brackets.empty();}

int main() { int n; std::cin >> n;

std::string sequence;    for (int i = 0; i < n; ++i) {        int operation;        std::cin >> operation;

    if (operation == 1) {            char bracket;            std::cin >> bracket;            sequence.push_back(bracket);        } else if (operation == 2) {            if (!sequence.empty())                sequence.pop_back();        } else if (operation == 3) {            if (!sequence.empty())                std::cout << sequence.back() << std::endl;        } else if (operation == 4) {            std::cout << (isBalanced(sequence) ? 'Yes' : 'No') << std::endl;        }    }

return 0;}

代码解释

1. isMatching(char opening, char closing) 函数: 这个函数接受两个字符作为参数，分别表示左括号和右括号。它会检查这两个括号是否匹配。

2. isBalanced(const std::string& sequence) 函数: 这个函数接受一个字符串作为参数，表示需要检查的括号序列。 - 首先，创建一个空的栈 brackets 来存储左括号。 - 遍历输入序列中的每个字符： - 如果遇到左括号，将其压入栈中。 - 如果遇到右括号，检查栈是否为空或栈顶元素是否与当前右括号匹配。如果不匹配，则序列不平衡，返回 false。如果匹配，则弹出栈顶元素。 - 最后，如果栈为空，则表示所有括号都匹配，返回 true；否则，返回 false。

3. main 函数: - 读取操作次数 n。 - 创建一个空字符串 sequence 来存储括号序列。 - 循环执行 n 次操作： - 读取操作类型 operation。 - 根据操作类型执行相应操作： - 1: 读取一个字符并将其添加到序列末尾。 - 2: 如果序列不为空，则删除序列末尾的字符。 - 3: 如果序列不为空，则输出序列末尾的字符。 - 4: 调用 isBalanced 函数检查序列是否平衡并输出结果。

总结

这个代码实现了一个简单但有效的括号匹配算法。你可以使用它来检查包含圆括号、方括号和花括号的表达式的语法正确性。