華為筆試——C++括弧匹配

題目：括弧匹配

題目來源：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 }

結果：