在C++中，可以使用栈（stack）数据结构来实现括号匹配的功能。括号匹配是一个常见的问题，主要用来检查字符串中的括号是否正确配对（例如大括号与大括号 {}、小括号与小括号 ()、尖括号与尖括号 <> 等）。
![图片[1]_利用C++栈结构实现括号匹配算法_知途无界](https://zhituwujie.com/wp-content/uploads/2025/02/d2b5ca33bd20250224095300.png)
下面是一个详细的代码示例和解释，展示了如何使用栈来实现括号匹配：
#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> 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> 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>#include <iostream> #include <stack> #include <string> #include <unordered_map>#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;}bool isMatchingPair(char open, char close) { unordered_map<char, char> matchPairs = { {'(', ')'}, {'{', '}'}, {'<', '>'} }; return matchPairs[open] == close; }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();}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(); }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;}int main() { string expr; cout << "请输入一个包含括号的表达式: "; getline(cin, expr); if (areBracketsBalanced(expr)) { cout << "括号匹配成功！" << endl; } else { cout << "括号匹配失败！" << endl; } return 0; }int main() { string expr; cout << "请输入一个包含括号的表达式: "; getline(cin, expr); if (areBracketsBalanced(expr)) { cout << "括号匹配成功！" << endl; } else { cout << "括号匹配失败！" << endl; } return 0; }
- 从用户输入读取包含括号的表达式。
- 调用
areBracketsBalanced函数检查括号是否匹配，并输出结果。
这段代码展示了如何使用栈数据结构来实现括号匹配，并提供了详细的注释和解释。希望这对你有所帮助！
© 版权声明
文中内容均来源于公开资料，受限于信息的时效性和复杂性，可能存在误差或遗漏。我们已尽力确保内容的准确性，但对于因信息变更或错误导致的任何后果，本站不承担任何责任。如需引用本文内容，请注明出处并尊重原作者的版权。
THE END
暂无评论内容