问题 1756 --算法5-5~5-8:广义表的基本操作

1756: 算法5-5~5-8:广义表的基本操作

时间限制: 1 Sec  内存限制: 32 MB
提交: 13  解决: 6
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][20kb]

题目描述

广义表是线性表的推广和扩展。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP中,广义表是基本的数据结构,甚至程序本身也可以被表示为一系列的广义表。
由于广义表列表中的数据元素可能具有不同的结构,因此难以用顺序存储结构表示,而通常采用链式存储结构,每个数据元素用一个结点来表示。而结点的结构可以为原子或列表,因此需要两种结构的结点。常用的广义表存储方式可以是头尾链表存储,其形式定义如下:
广义表的深度定义为广义表中括号的重数,是广义表的一种量度。通过递归算法可以求得广义表的深度,算法描述如下:
而广义表的复制同样也可以通过递归算法得到实现,算法描述如下:
广义表可以被表示成一个字符串,即广义表的书写形式。我们将会给出一个广义表的书写形式字符串,请通过如下所示的算法将其转换成广义表,并将得到的广义表复制为新的广义表,计算并输出新的广义表的深度。

输入

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

输出

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

样例输入

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

样例输出

3

提示

广义表作为线性表的推广,了解其存储方式和使用方法具有非常重要的意义。在本题中,你需要掌握字符串的基本操作,同时更需要理解广义表的结构和操作方法。

来源

[提交][状态]