#include<iostream>
#include<string>
using namespace std;

enum elemTag {ATOM,LIST}; 
class GList;

class GLnode
{
private:
    elemTag Tag; //标志是原子还是子表 0:原子 1:子表
    union 
    {
        char data; //原子结点值域
        struct //表结点指针域
        {
            GLnode *hp;
            GLnode *tp;
        }ptr;
    };
    friend class GList;
};

class GList
{
public:
    string Decompose(string &str)
    {
        //将非空串str分割成2部分，hstr为第一个‘,‘之前的子串，str为后面的
        int n,i,k;
        string ch,hstr;
        n=str.length();
        for(i=0,k=-1;i<n && (ch!="," || k!=0) ;i++)
        {
            //搜索最外层第一个逗号
            ch=str.substr(i,1); //从第i个位置起读1个字符
            if(ch=="(")
                ++k;
            else if(ch==")")
                --k;
        }
        if(i<n)
        {
            hstr=str.substr(1,i-2);//不要左括号，不要逗号，所以是i-2
            str="("+str.substr(i,n-i);
        }
        else
        {
            hstr=str.substr(1,n-2);
            str="";
        }
        return hstr;
    }

    /*----------------------------------------------------
    /从广义表书写形式串S创建采用头尾链表存储表示的广义表T
    /建立广义表头尾结点存储结构的递归定义：
    /基本项：当S为空串时，置空广义表
    /         当S为单字符串时，建立原子结点的子表
    /递归项：假设sub为脱去S最外层括号的子串，记为"s1,s2,s3,..,sn"
    /        每个si为非空字符串，对每个si建立一个表结点
    /--------------------------------------------------------*/

    void Create_GList(GLnode *&GL,string S) //创建广义表
    {
        string hsub;
        if(S=="()") //S为空串
        {
            GL=NULL;
        }
        else
        {
            
            GL=new GLnode;
            if(S.length()==1)
            {
                GL->Tag=ATOM;
                GL->data=http://www.mamicode.com/S[0];
            }
            else
            {
                GL->Tag=LIST;
                hsub=Decompose(S); //从S中分离出表头串hsub
                Create_GList(GL->ptr.hp,hsub);
                if(S.empty())
                {
                    GL->ptr.tp=NULL;
                }
                else
                {
                    Create_GList(GL->ptr.tp,S);
                }
            }
        }
    }
            
    int GList_Depth(GLnode *GL) //求广义表深度
    {
        /*-----------------------------------------
        /当广义表为空表时，深度为1，当广义表为原子时
        /深度为0，当广义表为广义表时，深度的求法为
        /GList_Depth(GL)=1+max{GList_Depth(lsi)}
        /-----------------------------------------*/

        if(!GL)
            return 1;
        if(GL->Tag==ATOM)
            return 0;
        int dep,max;
        GLnode *p;
        for(max=0,p=GL;p;p=p->ptr.tp)
        {
            dep=GList_Depth(p->ptr.hp);
            if(dep>max)
                max=dep;
        }
        return 1+max;
    }

    void Copy_GList(GLnode *GL,GLnode *&T) //T复制GL
    {
        //当表为空时，复制空表，否则先复制表头在复制表尾
        if(!GL)
            T=NULL;
        else
        {
            T=new GLnode;
            T->Tag=GL->Tag;
            if(GL->Tag==ATOM)
                T->data=http://www.mamicode.com/GL->data;
            else
            {
                Copy_GList(GL->ptr.hp,T->ptr.hp);
                Copy_GList(GL->ptr.tp,T->ptr.tp);
            }
        }
    }

    /*-----------------------------------------------
    /遍历广义表，如果是空表就输出"()"，如果遇到Tag=0
    /的结点，则直接输出该结点的值，如果tag=1，说明
    /是一个子表，首先输出左括号，然后递归调用输出数据
    /元素，并当表尾不空的时候输出逗号，最后输出右括号
    /-----------------------------------------------*/
    void Traverse_GList(GLnode *L)
    {
        if(!L)
            cout<<"()";
        else
        {
            if(L->Tag==ATOM)
                cout<<L->data;
            else
            {
                GLnode *p=NULL;
                cout<<‘(‘;
                p=L;
                while(p)
                {
                    Traverse_GList(p->ptr.hp);
                    p=p->ptr.tp;
                    if(p)
                        cout<<‘,‘;
                }
                cout<<‘)‘;
            }
        }
    }

    void GetHead(GLnode *GL) //取表头
    {
        //取广义表第一个元素
        cout<<"广义表：";
        Traverse_GList(GL);
        cout<<endl;
        if(!GL || GL->Tag==0 )
            cout<<"原子和空表不能去表头"<<endl;
        else
        {
            GLnode *h=GL->ptr.hp;
            if(h->Tag==ATOM)
                cout<<"表头为："<<h->data<<endl;
            else
            {
                cout<<"表头为：";
                Traverse_GList(h);
                cout<<endl;
            }
        }
    }
    
    void GetTail(GLnode *GL) //取表尾
    {
        //广义表表尾指的是除了第一个元素后所有剩余的元素组成的表
        cout<<"广义表：";
        Traverse_GList(GL);
        cout<<endl;

        if(!GL || GL->Tag==0)
            cout<<"原子和空表不能取表尾"<<endl;
        else
        {
            GLnode *t;
            t=GL->ptr.tp;
            cout<<"表尾为：";
            Traverse_GList(t);
            cout<<endl;
        }
    }
    
    int Length_GList_1(GLnode *GL) //求表长，非递归
    {
        //用非递归方式求广义表长度
        int len=0;
        if(GL && GL->Tag==LIST)
        {
            while(GL)
            {
                GL=GL->ptr.tp;
                len++;
            }
            return len;
        }
        else
            return 0;
    }

    int Length_GList_2(GLnode *GL) //求表长，递归
    {
        if(!GL)
            return 0;
        return 1+Length_GList_2(GL->ptr.tp);
    }

    void Replace_GList(GLnode *p,char x,char y,GLnode *&q) //替换
    {
        //将广义表p中元素x替换成y，构建新广义表q
        if(!p)
            q=NULL;
        else
        {
            if(p->Tag==ATOM)
            {
                q=new GLnode;
                q->Tag=ATOM;
                q->ptr.hp=NULL;
                if(p->data=http://www.mamicode.com/=x)
                    q->data=http://www.mamicode.com/y;
                else
                    q->data=http://www.mamicode.com/p->data;
            }
            else
            {
                GLnode *h,*t;
                Replace_GList(p->ptr.hp,x,y,h);//递归处理表头得到h
                Replace_GList(p->ptr.tp,x,y,t);//递归处理表尾得到t
                q=new GLnode;
                q->Tag=LIST;
                q->ptr.hp=h;
                q->ptr.tp=t;
            }
        }
    }

    int Is_Same(GLnode *p,GLnode *q)//判断是否相等
    {
        int flag=1;//1表示相等，0表示不相等
        if(p && q)
        {
            if(p->Tag==ATOM && q->Tag==ATOM)
            {
                if(p->data!=q->data)
                    flag=0;
                else
                    flag=1;
            }
            else if(p->Tag==LIST &&q->Tag==LIST)
                flag=Is_Same(p->ptr.hp,q->ptr.hp);
            else
                flag=0;
            if(flag)
                flag=Is_Same(p->ptr.tp,q->ptr.tp);
        }
        else
        {
            if(p && !q)
                flag=0;
            if(!p && q)
                flag=0;
        }
        return flag;
    }
    void Concat_Glist(GLnode *&GL,GLnode *LG) //连接两个广义表
    {
        GLnode *p=GL;
        GLnode *q=p->ptr.tp;
        while(q->ptr.tp)
            q=q->ptr.tp;
        q->ptr.tp=LG;
        GL=p;
    }

};

from:http://blog.csdn.net/jkay_wong/article/details/6683989