华为笔试——C++括号匹配

2021-06-29 20:06

阅读：518

标签：false bsp article 文章图片情况 detail 链接 cstring

题目：括号匹配

题目来源：https://blog.csdn.net/lizi_stdio/article/details/76618908

题目介绍：输入一个字符串，里面可能包含“（）”、“ [ ] ”、" { } "三种括号，要求程序判断这个字符串里的括号是否成对出现且嵌套关系正确，若成对出现且嵌套关系正确，或字符串中无括号出现时，输出True；否则输出False。无需考虑非法输入。

例：

输入：

（1+4）/[(2+3)*4]

输出：

True

分析：这个问题考察的其实是栈的问题。因为若要成对出现且嵌套关系正确，就必须满足最后的“（”后的下一个括号必须是“）”，否则就不正确，其他两种括号同理。在前面出现的“ [ ”后出现的可能是“（”或者是“ ] ”，因此需要用到栈来解决。若出现左括号则进栈，遇到下一个右括号则与栈中比较，若匹配则出栈进行下一个比对。这样直到末尾，若栈空则输出True，否则输出False即可。

代码：（转载，链接放在文章开头，写的真的很好）

 1 #include  2 #include  3 #include string>
 4 #include  5 #include  6 #include 
 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     vectorchar> 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 }

结果：

技术分享图片

华为笔试——C++括号匹配

标签：false bsp article 文章图片情况 detail 链接 cstring

原文地址：https://www.cnblogs.com/ljy1227476113/p/9644075.html

上一篇：数据结构及算法学习（一）

下一篇：Java并发编程高阶技术高性能并发框架源码解析与实战高清无密

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：华为笔试——C++括号匹配
文章链接：http://soscw.com/index.php/essay/99524.html

亲，登录后才可以留言！

华为笔试——C++括号匹配

评论

热门文章

推荐文章

最新文章

置顶文章