华为笔试——C++括号匹配
2018-09-18 06:24:31来源:博客园 阅读 ()
题目:括号匹配
题目来源: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 }
结果:
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash