1354 - 算法5-5~5-8：广义表的基本操作

游客 Signup | Login

中文 | En

1354 - 算法5-5~5-8：广义表的基本操作

通过次数

提交次数

旧版界面

Time Limit : 1 秒 Memory Limit : 32 MB

广义表是线性表的推广和扩展。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP中，广义表是基本的数据结构，甚至程序本身也可以被表示为一系列的广义表。

由于广义表列表中的数据元素可能具有不同的结构，因此难以用顺序存储结构表示，而通常采用链式存储结构，每个数据元素用一个结点来表示。而结点的结构可以为原子或列表，因此需要两种结构的结点。常用的广义表存储方式可以是头尾链表存储，其形式定义如下：

<span style="font-family:宋体;">广义表的深度定义为广义表中括号的重数，是广义表的一种量度。通过递归算法可以求得广义表的深度，算法描述如下：</span>

<img src="http://tk.hustoj.com:80/upload/pimg1756_2.png" width="625" height="198" alt="" />

<span style="font-family:宋体;">而广义表的复制同样也可以通过递归算法得到实现，算法描述如下：</span>

<img src="http://tk.hustoj.com:80/upload/pimg1756_3.png" width="486" height="342" alt="" />

<span style="font-family:宋体;">广义表可以被表示成一个字符串，即广义表的书写形式。我们将会给出一个广义表的书写形式字符串，请通过如下所示的算法将其转换成广义表，并将得到的广义表复制为新的广义表，计算并输出新的广义表的深度。</span>

<img src="http://tk.hustoj.com:80/upload/pimg1756_4.png" width="570" height="630" alt="" />

<span></span>

<span></span>

<span></span>

Input

输入只有一行，包含一个无空格的字符串S，即广义表的书写形式串。保证S为合法的广义表书写形式串，且S的长度不超过100。

Output

只有一个整数，即按照题目描述的过程得出的广义表的深度。请注意行尾输出换行。

Examples

Input Format

((),(e),(a,(b,c,d)))

Output Format

Solution C

int main(int argc, char* argv[])
{
  char str[100];
  int max,i,base;
  while(gets(str))
  {
	  max=base=0;
     for(i=0;str[i]!='\0';i++)
	 {
	   if(str[i]=='(')
	   { base++;
	     if(base>max)
			 max=base;
	   }
	   else if(str[i]==')')
		   base--;
	 }
	 printf("%d\n",max);
  }
	return 0;
}

Solution C++

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define MAXSTRLEN 200 /* 用户可在255以内定义最大串长（1个字节） */
typedef int Status; /* 函数结果状态代码,如OK等 */
typedef char SString[MAXSTRLEN+1]; /* 0号单元存放串的长度 */
typedef char AtomType; /* 定义原子类型为字符型 */
typedef enum{ATOM,LIST}ElemTag; /* ATOM==0:原子,LIST==1:子表 */
typedef struct GLNode {
	ElemTag tag; /* 公共部分,用于区分原子结点和表结点 */
	union { /* 原子结点和表结点的联合部分 */
		AtomType atom; /* atom是原子结点的值域,AtomType由用户定义 */
		struct {
			struct GLNode *hp,*tp;
		}ptr; /* ptr是表结点的指针域,prt.hp和ptr.tp分别指向表头和表尾 */
	}a;
}*GList,GLNode; /* 广义表的头尾链表存储表示 */
Status InitGList(GList *L) { /* 创建空的广义表L */
	*L=NULL;
	return OK;
}
Status CopyGList(GList *T,GList L) {
/* 采用头尾链表存储结构,由广义表L复制得到广义表T。算法5.6 */
	if(!L) { /* 复制空表 */
		*T=NULL;
	} else {
		*T=(GList)malloc(sizeof(GLNode)); /* 建表结点 */
		if(!*T) exit(OVERFLOW);
		(*T)->tag=L->tag;
		if(L->tag==ATOM) {
			(*T)->a.atom=L->a.atom; /* 复制单原子 */
		} else {
			CopyGList(&((*T)->a.ptr.hp),L->a.ptr.hp);
			/* 复制广义表L->ptr.hp的一个副本T->ptr.hp */
			CopyGList(&((*T)->a.ptr.tp),L->a.ptr.tp);
			/* 复制广义表L->ptr.tp的一个副本T->ptr.tp */
		}
	}
	return OK;
}
void DestroyGList(GList *L) { /* 广义表的头尾链表存储的销毁操作 */
	GList q1,q2;
	if(*L) {
		if((*L)->tag==ATOM) {
			free(*L); /* 删除原子结点 */
			*L=NULL;
		} else { /* 删除表结点 */
			q1=(*L)->a.ptr.hp;
			q2=(*L)->a.ptr.tp;
			free(*L);
			*L=NULL;
			DestroyGList(&q1);
			DestroyGList(&q2);
		}
	}
}
int GListDepth(GList L) { /* 采用头尾链表存储结构,求广义表L的深度。算法5.5 */
	int max,dep;
	GList pp;
	if(!L) return 1; /* 空表深度为1 */
	if(L->tag==ATOM) return 0; /* 原子深度为0 */
	for(max=0,pp=L;pp;pp=pp->a.ptr.tp) {
		dep=GListDepth(pp->a.ptr.hp); /* 求以pp->a.ptr.hp为头指针的子表深度 */
		if(dep>max) max=dep;
	}
	return max+1; /* 非空表的深度是各元素的深度的最大值加1 */
} // GListDepth
Status StrAssign(SString T,char *chars) { /* 生成一个其值等于chars的串T */
	int i;
	if(strlen(chars)>MAXSTRLEN) {
		return ERROR;
	} else {
		T[0]=strlen(chars);
		for(i=1;i<=T[0];i++) T[i]=*(chars+i-1);
		return OK;
	}
}
int StrLength(SString S) { /* 返回串的元素个数 */
	return S[0];
}
int StrCompare(SString S,SString T) { /* 初始条件: 串S和T存在 */
	/* 操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0 */
	int i;
	for(i=1;i<=S[0]&&i<=T[0];++i) if(S[i]!=T[i]) return S[i]-T[i];
	return S[0]-T[0];
}
Status SubString(SString Sub,SString S,int pos,int len) {
/* 用Sub返回串S的第pos个字符起长度为len的子串。算法4.3 */
	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[pos+i-1];
	Sub[0]=len;
	return OK;
}
Status StrCopy(SString T,SString S) { /* 由串S复制得串T */
	int i;
	for(i=0;i<=S[0];i++) T[i]=S[i];
	return OK;
}
Status ClearString(SString S) { /* 初始条件:串S存在。操作结果:将S清为空串 */
	S[0]=0;/* 令串长为零 */
	return OK;
}
Status StrEmpty(SString S) { /* 若S为空串,则返回TRUE,否则返回FALSE */
	if(S[0]==0)
	return TRUE;
	else
	return FALSE;
}
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 {
		*L=(GList)malloc(sizeof(GLNode));
		if(!*L) /* 建表结点 */
			exit(OVERFLOW);
		if(StrLength(S)==1) { /* S为单原子 */
			(*L)->tag=ATOM;
			(*L)->a.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->a.ptr.hp,hsub);
				q=p;
				if(!StrEmpty(sub)) { /* 表尾不空 */
					p=(GLNode *)malloc(sizeof(GLNode));
					if(!p) exit(OVERFLOW);
					p->tag=LIST;
					q->a.ptr.tp=p;
				}
			}while(!StrEmpty(sub));
			q->a.ptr.tp=NULL;
		}
	}
	return OK;
}

int main() {
	char p[201];
	SString t;
	GList l;
	InitGList(&l);
	gets(p);
	StrAssign(t,p);
	CreateGList(&l,t);
	printf("%d\n", GListDepth(l));
	DestroyGList(&l);
	return 0;
}

上一题下一题 Hint Code Discuss Stats