广义表

广义表的实现：
  1 #include<iostream>
  2 #include<assert.h>
  3 using namespace std;
  4 enum Type
  5 {
  6     HEAD,
  7     VALUE,
  8     SUB,
  9 };
 10 struct GeneralListNode
 11 {
 12     Type _type;
 13     GeneralListNode* next;
 14     union
 15     {
 16         char _value;
 17         GeneralListNode* _sublink;
 18     };
 19     GeneralListNode(Type type=VALUE, char value = 0) :_type(type), next(NULL)
 20     {
 21         if (_type == VALUE)
 22         {
 23             _value = value;
 24         }
 25         else if (_type == SUB)
 26         {
 27             _sublink = NULL;
 28         }
 29     }
 30 };
 31 class Generalist
 32 {
 33 
 34 public:Generalist() :_head(NULL) {}
 35        ~Generalist()  
 36        {
 37            _Destory(_head); 
 38        }
 39        Generalist(char* s) :_head(NULL)
 40        {
 41            _head = _CreateGeneraList(s);
 42        }
 43        size_t size()
 44        {
 45            return _size(_head);
 46        }
 47        size_t Depth()
 48        {
 49            return _Depth(_head);
 50        }
 51        void Print()
 52        {
 53            _Print(_head);
 54            cout << endl;
 55        }
 56 protected:
 57     GeneralListNode* _CreateGeneraList(char*& s)
 58     {
 59         assert(*s =='(');
 60         GeneralListNode* head = new GeneralListNode(HEAD);    
 61         ++s;
 62         GeneralListNode* cur = head;
 63 
 64 
 65         while (*s)
 66         {
 67             if (*s == '(')
 68             {
 69                 GeneralListNode* subNode = new GeneralListNode(SUB);
 70                 cur->next = subNode;
 71                 cur = cur->next;
 72                 subNode->_sublink = _CreateGeneraList(s);
 73             }
 74             else if (*s == ')')
 75             {
 76                 ++s;
 77                 break;
 78             }
 79             else if (ISvalue(*s))
 80             {
 81                 GeneralListNode* valueNode = new GeneralListNode(VALUE, *s);
 82                 cur->next = valueNode;
 83                 cur = cur->next;
 84                 ++s;
 85             }
 86             else
 87             {
 88                 ++s;
 89             }
 90         }
 91         return head;
 92     }
 93 protected:
 94     void _Destory(GeneralListNode* head)
 95     {
 96         GeneralListNode* cur = head;
 97         while (cur)
 98         {
 99             GeneralListNode* del = cur;
100             cur = cur->next;
101             if (del->_type == SUB)
102             {
103                 _Destory(del->_sublink);
104             }
105             delete del;
106         }
107     }
108     size_t _size(GeneralListNode* head)
109     {
110         GeneralListNode*cur = head;
111         size_t size = 0;
112 
113         while (cur)
114         {
115             if (cur->_type = VALUE)
116             {
117                 ++size;
118             }
119             else if (cur->_type = SUB)
120             {
121                 size += _size(cur->_sublink);
122             }
123             cur = cur->next;
124         }
125         return size;
126     }
127     void _Print(GeneralListNode* head)
128     {
129         GeneralListNode*cur = head;
130         while (cur)
131         {
132             if (cur->_type = HEAD)
133             {
134                 cout << "(";
135             }
136             else if (cur->_type = VALUE)
137             {
138                 cout << cur->_value;
139                 if (cur->next)
140                 {
141                     cout << ",";
142                 }
143             }
144             else
145             {
146                 _Print(cur->_sublink);
147                 if (cur->next)
148                 {
149                     cout << ",";
150                 }
151             }
152             cur = cur->next;
153         }
154         cout << ")";
155     }
156     size_t _Depth(GeneralListNode* head)
157     {
158         size_t depth = 1;
159         GeneralListNode* cur = head;
160 
161         while (cur)
162         {
163             if (cur->_type == SUB)
164             {
165                 size_t subDepth = _Depth(cur->_sublink);
166                 if (subDepth + 1 > depth)
167                 {
168                     depth = subDepth + 1;
169                 }
170             }
171             cur = cur->next;
172         }
173         return depth;
174     }
175 public:
176     bool ISvalue(char ch)
177     {
178         if ((ch >= '0'&&ch <= '9') || (ch >= 'a'&&ch <= 'z') || (ch >= 'A'&&ch <= 'Z'))
179         {
180             return true;
181         }
182         else
183         {
184             return false;
185         }
186     }
187 protected:
188     GeneralListNode* _head;
189 };
190 int main()
191 {
192     Generalist g1("()");
193     Generalist g2("(a,b)");
194     Generalist g3("(a,b，(c,d))");
195     Generalist g4("(a,b,(c,d),(e,(f),h))");
196     g4.Print();
197     cout << g4.size() << endl;
198     cout << g3.size() << endl;
199 
200     system("pause");
201     return 0;
202 }