华为笔试——C++括号匹配
程序员文章站
2022-06-28 10:31:07
题目:括号匹配 题目来源:https://blog.csdn.net/lizi_stdio/article/details/76618908 题目介绍:输入一个字符串,里面可能包含“()”、“ [ ] ”、" { } "三种括号,要求程序判断这个字符串里的括号是否成对出现且嵌套关系正确,若成对出现且 ......
题目:括号匹配
题目来源: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 }
结果: