《数据结构与算法》课程设计
40、括号匹配的检验
问题描述：
假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）[ ]）或[（[ ] [ ]）]等为正确格式，[（ ]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列：
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“[”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“[”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，…… ，依次类推。可见这个处理过程正好和栈的特点相吻合。
基本要求：
读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。
测试数据：
输入（[ ]（）），结果“匹配”
输入 [（ ）]，结果“此串括号匹配不合法”
#include <iostream>
#include <stack>
#include <string>using namespace std;/*** 判定括号序列是否合法* @param str 括号序列* @return 返回栈是否为空*/
bool judge(const string &str) {
stack<char> s;for (char i : str) {
switch (i) {
case '(':s.push(i); //进栈break;case '[':s.push(i); //进栈break;case '{':s.push(i); //进栈break;case ')':if (s.top() != '(') //与栈顶括号不匹配return false;else //与栈顶括号匹配s.pop(); //栈顶括号出栈break;case ']':if (s.top() != '[') //与栈顶括号不匹配return false;else //与栈顶括号匹配s.pop(); //栈顶括号出栈break;case '}':if (s.top() != '{') //与栈顶括号不匹配return false;else //与栈顶括号匹配s.pop(); //栈顶括号出栈break;default:break;}}return s.empty();
}int main() {
string str;cout << "请输入括号序列:\n";cin >> str;if (judge(str))cout << "匹配" << endl;elsecout << "此串括号匹配不合法" << endl;return 0;
}