#include<stdio.h>
 #include<stdlib.h>
 #include<malloc.h>
 #define OK 0
 #define FALSE -1
 #define OVERFLOW -2
 #define Status int  
 #define MAXSTRLEN 255
 #define SElemType unsigned char  
 #define AtomType char
 typedef struct{
 SElemType *base;
 int Ssize;
 }Sstring;
 Sstring S,sub,hsub;
 //定义广义表的头尾链式 存储
typedef enum{ATOM,LIST} ElemTag;
 typedef struct GLNode{
 ElemTag tag;
 union {
   AtomType atom;
   struct {
    struct GLNode *hp,*tp;
   }ptr;
 };
 }*GList;
 GList  L;
 Status CreateGList(GList &L,Sstring &S);
 Status sever(Sstring &str,Sstring &hstr);
 Status StrLength(Sstring &S);
 Status SubString(Sstring &Sub,Sstring &S,int pos,int i);
 char SubString1(Sstring &str,int i, int long);
 Status Strcopy(Sstring &S1,Sstring &S2);
 Status ClearString(Sstring &S);
 Status StrEmpty(Sstring &S);
 Status InitString(Sstring &S);
 Status Create_String(Sstring &S,char a[255]);
 Status InitGList(GList L);
 Status StrCompare(Sstring &S1);
 void output_String(Sstring &S);
 void output_GLNode(GList L);
 Status Traverse_GList(GList L);
 int GListDepth(GList L);

 //由广义表的书写形式串 S 创建广义表 L
 Status  CreateGList(GList &L,Sstring &S){
 GList p,q;
 if(StrCompare(S)) {     
   L=NULL;
   }   // 相同，返回 1
 else{
   if(!(L=(GList)malloc(sizeof(GLNode))))  exit(OVERFLOW);
   if(StrLength(S)==1){//直接取得是S.base[0]的值
   L->tag=ATOM;
    L->atom=S.base[1];
   // printf("%c\n",L->atom);
   }
   else{
    L->tag=LIST;  p=L;
    SubString(sub,S,2,StrLength(S)-2);
   // output_String(sub);
    do{
     sever(sub,hsub);
     output_String(hsub);
     output_String(sub);
     CreateGList(p->ptr.hp,hsub);q=p;
     if(!StrEmpty(sub)){
      if(!(p=(GLNode *)malloc(sizeof(GLNode))))
        exit(OVERFLOW);
        p->tag=LIST;q->ptr.tp=p;
     }
    }while(!StrEmpty(sub));
     q->ptr.tp=NULL;
   }
 }
 return OK;
 }
 Status sever(Sstring &str,Sstring &hstr){
 //将非空串str分割为两个部分，hstr为第一个，之前的字串，str为之后的字串
int i,k,n;
 char ch;
 n=StrLength(str);
 i=1;
 k=0;
 ch=SubString1(str,i,1); //k记录尚未配对的左括号数
for( ;i<=n&&(ch!=','||k!=0);i++){
   ch=SubString1(str,i,1);
   if(ch=='(')  ++k;
   else if(ch==')') --k;
 }
 if((i-1)<n){
   SubString(hstr,str,1,i-2);
   SubString(str,str,i,n-i+1);
 }
 else{
   Strcopy(hstr,str);
   ClearString(str);
 }
 return OK;
 }
 /*Status sever(Sstring &str,Sstring &hstr){
 int n,i=0,k=0;
 char ch;
 n=StrLength(str);
 do{
   ++i;
   ch=SubString1(str,i,1);
   if(ch=='(') ++k;
   else if(ch==')') --k;
 }while(i<n&&(ch!=','||k!=0));
 if(i<n){
   SubString(hstr,str,1,i-1);
   SubString(str,str,i+1,n-i);
 }
 else{
   Strcopy(hstr,str);
   ClearString(str);
 }
 return OK;
 }*/
 Status StrLength(Sstring &S){
 return S.base[0];
 }
 Status SubString(Sstring &Sub,Sstring &S,int pos,int i){
     int temp;
 if((pos+i-1)>S.base[0])
    return FALSE;
 else{
   Sub.base[0]=i;
   for(temp=1;temp<=i;temp++){
    Sub.base[temp]=S.base[pos];
    pos++;
   }
 }  
 return OK;
 }
 //取字符串 str的第 i+1的位置值
char SubString1(Sstring &str,int i, int long){
 char ch;
 ch=str.base[i];
 return ch;
 }
 //将 S2复制给 S1
 Status Strcopy(Sstring &S1,Sstring &S2){
     int i;
 for(i=0;i<=S2.base[0];i++){
   S1.base[i]=S2.base[i];
 }
 return OK;
 }
 Status StrCompare(Sstring &S){
 if(S.base[0]!=2) return 0;
 else{
 if((S.base[1]=='(')&&(S.base[2]==')'))
    return 1;
     else return 0;
      }
 }
 Status ClearString(Sstring &S){
 S.base[0]=0;
 return OK;
 }
 Status StrEmpty(Sstring &S){
 if(S.base[0]==0) return 1;
   return 0;
 }
 Status InitGList(GList L){
 L=NULL;
 return OK;
 }
 Status InitString(Sstring &S){
 S.base=(SElemType *)malloc((MAXSTRLEN+1)*sizeof(SElemType));
 if(!S.base) exit(OVERFLOW);
 S.Ssize=MAXSTRLEN+1;
 S.base[0]=0;//0表示的是实数0，'0'表示的是字符
return OK;
 }
 /*int  Create_String(Sstring &S){
     int ch;
 int i=0;
 ch=getchar();
 while(i<S.Ssize){
    if(ch!=EOF){
     i++;
     S.base[0]=S.base[0]+1;
   S.base[i]=ch;
   ch=getchar();
    }
    else  return OK;
     }
 }*/
 int Create_String(Sstring &S,char a[255]){
 int i,n; char *c;
 for(i=0,c=a;*c!='\0';){
   i++;
   c++;
 }
 printf("%d\n",i);
 if(!i){
   S.base[0]=0;
 }
 else{
   S.base[0]=i;
   for(n=0;n<i;n++){
    S.base[n+1]=a[n];
   }
 }
 return OK;
 }

 Status Traverse_GList(GList L){
 if(!L) ;
 else{
   if(L->tag==ATOM)
      output_GLNode(L);
   else{
    Traverse_GList(L->ptr.hp);
    Traverse_GList(L->ptr.tp);
   }   
 }
 return OK;
 }
 void output_String(Sstring &S){
 int i;
 printf("%d\n",S.base[0]);
 for(i=1;i<=S.base[0];i++){
   printf("%c",S.base[i]);
 }
 printf("\n");
 }
 void output_GLNode(GList L){
 printf("%c",L->atom);
 }
 int GListDepth(GList L){
 int max,dep;
 GList pp;
 if(!L) return 1;
 if(L->tag==ATOM) return 0;
 for(max=0,pp=L;pp;pp=pp->ptr.tp){
   dep=GListDepth(pp->ptr.hp);
   printf("%d ",dep);
   if(dep>max) max=dep;
 }
 return max+1;
 }
 int main(){
 int Depth;
 //为什么碰到（e），（a）这样的情况就不行；  
 //char a[255]="((),a,(e),(a,(b,c,d)))";
    //(2)char a[255]="((),a,(e),((d)))";
   //(1) char a[255]="(((a)),b,(d))";
     
   // 也是正确的//
    char  a[255]="(a,c,x,e,(s))";  
 //几种特殊的情况  都是正确的
//char a[255]="(a)";
 //char a[255]="a";
 // char a[255]="()";
   InitGList(L);
 InitString(S);InitString(sub);InitString(hsub);
 Create_String(S,a);
 output_String(S);
 CreateGList(L,S);
 printf("%d\n",L);
 printf("output the equal members:\n");
 Traverse_GList(L);
 printf("\n");
 Depth=GListDepth(L);
 printf("\n");
 printf("The Depth of the GList is:%d\n",Depth);
 system("pause");
 return 0;
 }

//运行时，像（a,b,c,(e)）这样的情况就可以。只要碰到像（（e），（x））的就不行，不会把（x）链接到链表中