1 条题解
-
0
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; }
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; }
- 1
信息
- ID
- 1694
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者