题目：括号匹配
题目来源：https://blog.csdn.net/lizi_stdio/article/details/76618908
题目介绍：输入一个字符串，里面可能包含“（）”、“ [ ] ”、" { } "三种括号，要求程序判断这个字符串里的括号是否成对出现且嵌套关系正确，若成对出现且嵌套关系正确，或字符串中无括号出现时，输出True；否则输出False。无需考虑非法输入。
例：
输入：
（1+4）/[(2+3)*4]
输出：
True
分析：这个问题考察的其实是栈的问题。因为若要成对出现且嵌套关系正确，就必须满足最后的“（”后的下一个括号必须是“）”，否则就不正确，其他两种括号同理。在前面出现的“ [ ”后出现的可能是“（”或者是“ ] ”，因此需要用到栈来解决。若出现左括号则进栈，遇到下一个右括号则与栈中比较，若匹配则出栈进行下一个比对。这样直到末尾，若栈空则输出True，否则输出False即可。
代码：（转载，链接放在文章开头，写的真的很好）
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <map> 5 #include <vector> 6 #include <algorithm> 7 using namespace std; 8 9 bool isLeft(char a) 10 { 11 return (a == '(') || (a == '[') || (a == '{'); 12 } 13 14 bool isRight(char a) 15 { 16 return (a == ')') || (a == ']') || (a == '}'); 17 } 18 19 bool isMatch(char a, char b) 20 { 21 if (a == '('&&b == ')') 22 { 23 return true; 24 } 25 else if (a == '['&&b == ']') 26 { 27 return true; 28 } 29 else if (a == '{'&&b == '}') 30 { 31 return true; 32 } 33 return false; 34 } 35 36 int main() 37 { 38 #if 0 39 freopen("in.txt", "r", stdin); 40 //freopen("out.txt", "w", stdout); 41 #endif 42 string str; 43 vector<char> cvec; 44 cvec.reserve(200); 45 while (cin >> str) 46 { 47 auto iter = str.begin(); 48 for (; iter != str.end(); ++iter) 49 { 50 //左括号直接进栈 51 if (isLeft(*iter)) 52 { 53 cvec.push_back(*iter); 54 } 55 //如果出现右括号 56 else if (isRight(*iter)) 57 { 58 //不合理情况1： 栈空的话，直接退出 这里情况一开始忘记考虑，但是华为机试仍然100%通过 59 if (cvec.empty()) 60 { 61 break; 62 } 63 char c = cvec.back(); 64 cvec.pop_back(); 65 //不合理情况2：判断栈中左括号与现在的右括号是否匹配 66 if (!isMatch(c, *iter)) 67 { 68 break; 69 } 70 } 71 } 72 //处理不合理情况1，2 以及不合理情况3：字符已经遍历结束，但是栈仍然非空 73 if (iter != str.end() || !cvec.empty()) 74 { 75 cout << "false" << endl; 76 } 77 else 78 { 79 cout << "true" << endl; 80 } 81 } 82 return 0; 83 }
结果：
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
