// bo5-51.cpp 廣義表的書寫形式串為SString類型
 #include"c4-1.h" // 定義SString類型
 #include"bo4-1.cpp" // SString類型的基本操作
 void sever(SString str,SString hstr) // 算法5.8 SString是數組，不需引用類型
 { // 將非空串str分割成兩部分:hsub為第一個','之前的子串,str為之后的子串
   int n,k,i; // k記尚未配對的左括號個數
   SString ch,c1,c2,c3;
   n=StrLength(str);
   StrAssign(c1,",");
   StrAssign(c2,"(");
   StrAssign(c3,")");
   SubString(ch,str,1,1);
   for(i=1,k=0;i<=n&&StrCompare(ch,c1)||k!=0;++i)
   { // 搜索最外層的第一個逗號
     SubString(ch,str,i,1);
     if(!StrCompare(ch,c2))
       ++k;
     else if(!StrCompare(ch,c3))
       --k;
   }
   if(i<=n)
   {
     SubString(hstr,str,1,i-2);
     SubString(str,str,i,n-i+1);
   }
   else
   {
     StrCopy(hstr,str);
     ClearString(str);
   }
 }

 Status CreateGList(GList &L,SString S) // 算法5.7
 { // 采用頭尾鏈表存儲結構,由廣義表的書寫形式串S創建廣義表L。設emp="()"
   SString sub,hsub,emp;
   GList p,q;
   StrAssign(emp,"()");
   if(!StrCompare(S,emp))
     L=NULL; // 創建空表
   else
   {
     if(!(L=(GList)malloc(sizeof(GLNode)))) // 建表結點
       exit(OVERFLOW);
     if(StrLength(S)==1) // S為單原子
     {
       L->tag=ATOM;
       L->atom=S[1]; // 創建單原子廣義表
     }
     else
     {
       L->tag=LIST;
       p=L;
       SubString(sub,S,2,StrLength(S)-2); // 脫外層括號
       do
       { // 重復建n個子表
         sever(sub,hsub); // 從sub中分離出表頭串hsub
         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;
 }