#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR -1
#define OVERFLOW 0
#define TRUE 1 
#define FALSE 0
#define MAXSTRLEN 255

typedef int Status;
typedef unsigned char SString[MAXSTRLEN+1];

typedef int ElemType;
typedef int AtomType;
typedef enum {ATOM, LIST}ElemTag;
typedef struct GLNode{
	int mark;
	ElemTag tag;
	union{
		AtomType atom;
		struct {struct GLNode *hp, *tp;}ptr;
	};
}*GList, GLNode;

Status StrAssign(SString T, unsigned char *chars)
{
	int i = 0;
	int n;
	 	
	while(*(chars + i))
	{
		if(i < MAXSTRLEN)
		{
			n = i + 1;
			T[n] = *(chars + i);
			i++;
		}
		else
			break;
	}
	T[0] = i;
	return OK;
}

Status StrCompare(SString S, SString T)
{
	int i=1;
	if(S[0]>0 && T[0]>0)
	{
		while(i<=S[0] && i<=T[0])
		{
			if(S[i] > T[i])
				return 11;
			else if(S[i] < T[i])
				return -11;
			else
				i++;
		}
		if(S[0]>T[0])
			return 11;
		else if(S[0]<T[0])
			return -11;
		else
			return 10; 
	}
	else
		return ERROR;
}

int StrLength(SString S)
{
	return S[0];
}

Status SubString(SString Sub, SString S, int pos, int len)
{
	int i;
	if(pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
	{
		return ERROR;
	}
	for(i=1; i<=len; i++)
	{
		Sub[i] = S[i+pos-1];
	}
	Sub[0] = len;
	return OK;
}

Status StrEmpty(SString S)
{
	if(S[0] == 0)
		return TRUE;
	else
		return FALSE;
}

Status StrCopy(SString T, SString S)
{
	int i;
	for(i=1; i<=S[0]; i++)
	{
		T[i] = S[i];
	}
	T[0] = S[0];
	return OK;
}

Status ClearString(SString S)
{
	S[0] = 0;
	return OK;
}

Status server(SString str, SString hstr)
{
	int n = StrLength(str);
	int i = 0;
	int k = 0;
	SString ch;

	do{
		i++;
		SubString(ch, str, i, 1);
		if(ch[1] == '(')
			k++;
		else if(ch[1] == ')')
			k--;
	}while(i<n && (ch[1]!=',' || 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;
}

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);
		if(dep>max)
			max = dep;
	}
	return max+1;
}

Status CopyGList(GList *T, GList L)
{
	if(!L)
		*T = NULL;
	else
	{
		if(!(*T=(GList)malloc(sizeof(GLNode))))
			exit(OVERFLOW);
		(*T)->tag = L->tag;
		if(L->tag == ATOM)
			(*T)->atom = L->atom;
		else
		{
			CopyGList(&(*T)->ptr.hp, L->ptr.hp);
			CopyGList(&(*T)->ptr.tp, L->ptr.tp);
		}
	}
	return OK;
}

Status CreateGList(GList *L, SString S)
{
	unsigned char *nlgl = "()";
	GList p, q;
	SString emp, sub, hsub;
	StrAssign(emp, nlgl);
	
	if(StrCompare(S, emp) == 10)
		*L = NULL;
	else
	{
		if(!(*L=(GList)malloc(sizeof(GLNode))))
			exit(OVERFLOW);
		if(StrLength(S)==1)
		{
			(*L)->tag = ATOM;
			(*L)->atom = S[1];
		}
		else
		{
			(*L)->tag = LIST;
			p = (*L);
			SubString(sub, S, 2, StrLength(S)-2);
			do{
				server(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;
		}
		(*L)->mark = 0;
	}
	return OK;
}

void MarkList(GList GL)
{
	GList p, q, t;
	_Bool finished;

	t = NULL;
	p = GL;
	finished = FALSE;
	while(!finished)
	{
		while(p->mark == 0)
		{
			p->mark = 1;
			q = p->ptr.hp;
			if(q && q->mark==0)
			{
				if(q->tag == 0)
					q->mark = 1;
				else
				{
					p->ptr.hp = t;
					p->tag = 0;
					t = p;
					p = q;
				}
			}
		}
		q = p->ptr.tp;
		if(q && q->mark==0)
		{
			p->ptr.tp = t;
			t = p;
			p = q;
		}
		else
		{
			while(t && t->tag==1)
			{
				q = t;
				t = q->ptr.tp;
				q->ptr.tp = p;
				p = q;
			}
			if(!t)
				finished = TRUE;
			else
			{
				q = t;
				t = q->ptr.hp;
				q->ptr.hp = p;
				p = q;
				p->tag =1;
			}
		}
	}
}

int main(void)
{
	GList L, T;
	SString S;
	unsigned char *ss = "((),(e),(a,(b,c,d)))";
	StrAssign(S, ss);

	CreateGList(&L, S);
	printf("GList Depth of L: %d\n", GListDepth(L));

	CopyGList(&T, L);
	printf("GList Depth of T: %d\n", GListDepth(T));

	MarkList(L);
	return OK;
}