//Generalized.h#pragmaonce#ifndef__GENERALIZED_H__#define__GENERALIZED_H__enumType{HEAD,VALUE,SUB,};structGeneralizedNode{Type_type;GeneralizedNode*_next;union{int_value;GeneralizedNode*_sublink;};GeneralizedNode(){}GeneralizedNode(Typetype,constintvalue=0):_type(type),_next(NULL),_value(value){}};classGeneralized{public:Generalized();Generalized(constchar*str);Generalized(constGeneralized&g);Generalized&operator=(constGeneralized&g);~Generalized();voidPrint()const;size_tSize()const;size_tLength()const;size_tDepth()const;protected:GeneralizedNode*_CreateList(constchar*&str);GeneralizedNode*_Copy(GeneralizedNode*head);void_Destory(GeneralizedNode*head);void_PrintGeneral(GeneralizedNode*head)const;size_t_SizeGeneralized(GeneralizedNode*head)const;size_t_DepthGeneralized(GeneralizedNode*head)const;protected:GeneralizedNode*_head;};#endif/*__GENERALIZED_H__*/

Generalized.cpp:

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>#include"Generalized.h"#include<assert.h>Generalized::Generalized():_head(NULL){}Generalized::Generalized(constchar*str):_head(NULL){_head=_CreateList(str);}GeneralizedNode*Generalized::_CreateList(constchar*&str){assert(str);while(isspace(*str)){++str;}assert(*str=='(');//D=(a,b,(c,d),(e,(f),h))GeneralizedNode*head=newGeneralizedNode(HEAD);GeneralizedNode*cur=head;++str;while(*str!='\0'){if(*str=='('){cur->_next=newGeneralizedNode(SUB);cur=cur->_next;cur->_sublink=_CreateList(str);}elseif((*str>='0'&&*str<='9')||(*str>='a'&&*str<='z')||(*str>='A'&&*str<='Z')){cur->_next=newGeneralizedNode(VALUE,*str);cur=cur->_next;++str;}elseif(*str==')'){++str;break;}else{++str;}}returnhead;}Generalized::Generalized(constGeneralized&g){this->_head=this->_Copy(g._head);}GeneralizedNode*Generalized::_Copy(GeneralizedNode*head){assert(head);GeneralizedNode*cur=head;GeneralizedNode*retHead=NULL;GeneralizedNode*tmp=NULL;while(cur){if(cur->_type==HEAD){retHead=newGeneralizedNode(HEAD);tmp=retHead;}elseif(cur->_type==VALUE){tmp->_next=newGeneralizedNode(VALUE,cur->_value);tmp=tmp->_next;}elseif(cur->_type==SUB){tmp->_next=newGeneralizedNode(SUB);tmp->_next->_sublink=_Copy(cur->_sublink);tmp=tmp->_next;}cur=cur->_next;}returnretHead;}Generalized&Generalized::operator=(constGeneralized&g){if(this->_head!=g._head){this->_Destory(this->_head);this->_Copy(g._head);}return*this;}Generalized::~Generalized(){this->_Destory(this->_head);}voidGeneralized::_Destory(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){GeneralizedNode*del=cur;cur=cur->_next;if(del->_type==SUB){_Destory(del->_sublink);}deletedel;del=NULL;}}voidGeneralized::Print()const{this->_PrintGeneral(this->_head);}voidGeneralized::_PrintGeneral(GeneralizedNode*head)const{assert(head);GeneralizedNode*cur=head;while(cur){if(cur->_type==HEAD){std::cout<<"(";}elseif(cur->_type==VALUE){std::cout<<(char)cur->_value;if(cur->_next){std::cout<<",";}}elseif(cur->_type==SUB){//(a,b,(c,d),(e,(f),h))_PrintGeneral(cur->_sublink);if(cur->_next){std::cout<<",";}}cur=cur->_next;}std::cout<<")";}size_tGeneralized::Size()const{returnthis->_SizeGeneralized(this->_head);}size_tGeneralized::_SizeGeneralized(GeneralizedNode*head)const{if(head==NULL){return0;}size_tiCount=0;GeneralizedNode*cur=head;while(cur){if(cur->_type==VALUE){++iCount;}elseif(cur->_type==SUB){iCount+=_SizeGeneralized(cur->_sublink);}cur=cur->_next;}returniCount;}size_tGeneralized::Length()const{if(this->_head==NULL){return0;}GeneralizedNode*cur=this->_head->_next;size_tiCount=0;while(cur){++iCount;cur=cur->_next;}returniCount;}size_tGeneralized::Depth()const{returnthis->_DepthGeneralized(this->_head);}size_tGeneralized::_DepthGeneralized(GeneralizedNode*head)const{assert(head);//D=(a,b,(c,d),(e,(f),h))GeneralizedNode*cur=head;size_tmax=0;size_td=0;while(cur){if(cur->_type==SUB){d=_DepthGeneralized(cur->_sublink);if(max<d){max=d;}}cur=cur->_next;}returnmax+1;}