Loading... **这题是学校OJ的一题，弄了很久都没过就一直放那，现在学了栈就顺手把它解决了，期间也是历经坎坷啊。本来感觉OK了，结果还是有毛病，最后学长给了一个测试数据改了之后就解决了。。。** 括号的匹配 1000(ms) 65535(kb) 362 / 1985 题意描述： 在算术表达式中，除了加、减、乘、除等运算外，往往还有括号。包括有大括号{}，中括号[]，小括号()，尖括号<>等。 对于每一对括号，必须先左边括号，然后右边括号；如果有多个括号，则每种类型的左括号和右括号的个数必须相等；对于多重括号的情形，按运算规则，从外到内的括号嵌套顺序为：大括号->中括号->小括号->尖括号。例如，{[()]}，{()},{{}}为一个合法的表达式，而([{}])，{([])},[{<>}]都是非法的。 输入 文件的第一行为一个整数n（1≤n≤100），接下来有n行仅由上述四类括号组成的括号表达式。第i+1行表示第i个表达式。每个括号表达式的长度不超过255。 输出 在输出文件中有N行，其中第I行对应第I个表达式的合法性，合法输出YES，非法输出NO。 样例输入 5 {[(<>)]} [()] <>()[]{} [{}] {()} 样例输出 YES YES YES NO YES ```CPP #include <iostream> #include <stack> #include <string> #include <cstring> using namespace std; int isMax(char a, char b) { if (a == '{' && (b == '{' || b == '[' || b == '(' || b == '<')) { return 1; } else if (a == '[' && (b == '[' || b == '(' || b == '<')) { return 1; } else if (a == '(' && (b == '<' || b == '(')) { return 1; } else if(a == '<' && b =='<') { return 1; } else if (b == '}' && (a == '}' || a == ']' || a == ')' || a == '>')) { return 1; } else if (b == ']' && (a == ']' || a == ')' || a == '>')) { return 1; } else if (b == ')' && (a == '>' || a == ')')) { return 1; } else if (b == '>' && a == '>') { return 1; } else { return 0; } } int isKh(char a,char b) { if ((a == '{' || a == '[' || a == '<' || a == '(') && (b == '{' || b == '[' || b == '<' || b == '(')) return 1; else if ((a == '}' || a == ']' || a == '>' || a == ')') && (b == '}' || b == ']' || b == '>' || b == ')')) return 1; else return 0; } int main() { int n; cin >> n; while (n--) { string str; stack <char> s; cin >> str; int len = str.length(); if (len % 2 != 0) { cout << "NO" << endl; continue; } int flag = 0; for (int i = 0; i < len-1; i++) //判断是否有等级不合适的 { if (isKh(str[i], str[i + 1])) { if (!isMax(str[i], str[i + 1])) { cout << "NO" << endl; flag = 1; break; } } } if (flag) { continue; } for (int i = 0; i < len ; i++) { if (str[i] == '}' && !s.empty()) { if (s.top() == '{') { s.pop(); continue; } } if (str[i] == ']' && !s.empty()) { if (s.top() == '[') { s.pop(); continue; } } if (str[i] == ')' && !s.empty()) { if (s.top() == '(') { s.pop(); continue; } } if (str[i] == '>' && !s.empty()) { if (s.top() == '<') { s.pop(); continue; } } s.push(str[i]); } if (!s.empty()) { cout << "NO" << endl; } else { cout << "YES" << endl; } } system("pause"); return 0; } ``` 最后修改：2019 年 03 月 01 日 12 : 36 AM © 允许规范转载 赞赏 如果觉得我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 支付宝支付 微信支付
