第7节 栈的应用举例——括号匹配的检验

 1 /* 主题: 括号匹配的检验（使用栈）
 2 * 作者: chinazhangjie(邮箱:[email protected])
 3 * 开发语言: C++
 4 * 开发环境: Microsoft Visual Studio 2008
 5 * 日期: 2010.09.01
 6  */　　　　　
 7 #include "stack.h"    // for stack<T>
 8 class brac_matching {
 9     typedef unsigned int bm_size;
10 public:
11     // 构造函数
12     brac_matching() {}
13     brac_matching(const brac_matching& bm) {
14         elem = bm.elem;
15     }
16 
17     // 判断是否匹配
18     bool is_matching() const {
19         return size() == 0;
20     }
21 
22     // 增加括号
23     void add_brac(const char& c) {
24         if (size() == 0) {
25             // 直接入栈
26             elem.push(c);
27             return ;
28         }
29         if (is_matching(elem.get_top(),c)) {
30             // 匹配
31             elem.pop();
32         }
33         else {
34             elem.push(c);
35         }
36     }
37 
38     // 获得括号个数
39     bm_size size() const {
40         return elem.size();
41     }
42 
43     // 清空所有括号
44     void clear() {
45         elem.clear();
46     }
47 
48     // 重载赋值运算符
49     brac_matching& operator = (const brac_matching & rhs) {
50         if (this == &rhs)
51             return *this;
52         elem = rhs.elem;
53         return *this;
54     }
55 
56 private:
57     // 判断一对括号是否匹配
58     bool is_matching(const char& c1,const char& c2) {
59         if (c1 == '[' && c2 == ']'
60             || c1 == '(' && c2 == ')'
61             || c1 == '[' && c2 == ']')
62             return true;
63         else 
64             return false;
65     }
66 private:
67     stack<char> elem;
68 };