using namespace std;
enum Type
{
HEAD,
VALUE,
SUB,
};
struct GeneralListNode
{
Type _type;
GeneralListNode* next;
union
{
char _value;
GeneralListNode* _sublink;
};
GeneralListNode(Type type=VALUE, char value = 0) :_type(type), next(NULL)
{
if (_type == VALUE)
{
_value = value;
}
else if (_type == SUB)
{
_sublink = NULL;
}
}
};
class Generalist
{
public:Generalist() :_head(NULL) {}
~Generalist()
{
_Destory(_head);
}
Generalist(char* s) :_head(NULL)
{
_head = _CreateGeneraList(s);
}
size_t size()
{
return _size(_head);
}
size_t Depth()
{
return _Depth(_head);
}
void Print()
{
_Print(_head);
cout << endl;
}
protected:
GeneralListNode* _CreateGeneraList(char*& s)
{
assert(*s ==‘(‘);
GeneralListNode* head = new GeneralListNode(HEAD);
++s;
GeneralListNode* cur = head;
while (*s)
{
if (*s == ‘(‘)
{
GeneralListNode* subNode = new GeneralListNode(SUB);
cur->next = subNode;
cur = cur->next;
subNode->_sublink = _CreateGeneraList(s);
}
else if (*s == ‘)‘)
{
++s;
break;
}
else if (ISvalue(*s))
{
GeneralListNode* valueNode = new GeneralListNode(VALUE, *s);
cur->next = valueNode;
cur = cur->next;
++s;
}
else
{
++s;
}
}
return head;
}
protected:
void _Destory(GeneralListNode* head)
{
GeneralListNode* cur = head;
while (cur)
{
GeneralListNode* del = cur;
cur = cur->next;
if (del->_type == SUB)
{
_Destory(del->_sublink);
}
delete del;
}
}
size_t _size(GeneralListNode* head)
{
GeneralListNode*cur = head;
size_t size = 0;
while (cur)
{
if (cur->_type = VALUE)
{
++size;
}
else if (cur->_type = SUB)
{
size += _size(cur->_sublink);
}
cur = cur->next;
}
return size;
}
void _Print(GeneralListNode* head)
{
GeneralListNode*cur = head;
while (cur)
{
if (cur->_type = HEAD)
{
cout << "(";
}
else if (cur->_type = VALUE)
{
cout << cur->_value;
if (cur->next)
{
cout << ",";
}
}
else
{
_Print(cur->_sublink);
if (cur->next)
{
cout << ",";
}
}
cur = cur->next;
}
cout << ")";
}
size_t _Depth(GeneralListNode* head)
{
size_t depth = 1;
GeneralListNode* cur = head;
while (cur)
{
if (cur->_type == SUB)
{
size_t subDepth = _Depth(cur->_sublink);
if (subDepth + 1 > depth)
{
depth = subDepth + 1;
}
}
cur = cur->next;
}
return depth;
}
public:
bool ISvalue(char ch)
{
if ((ch >= ‘0‘&&ch <= ‘9‘) || (ch >= ‘a‘&&ch <= ‘z‘) || (ch >= ‘A‘&&ch <= ‘Z‘))
{
return true;
}
else
{
return false;
}
}
protected:
GeneralListNode* _head;
};
int main()
{
Generalist g1("()");
Generalist g2("(a,b)");
Generalist g3("(a,b,(c,d))");
Generalist g4("(a,b,(c,d),(e,(f),h))");
g4.Print();
cout << g4.size() << endl;
cout << g3.size() << endl;
system("pause");
return 0;
}广义表
原文:http://www.cnblogs.com/yuanshuang/p/5402163.html