题目来源：改编自严蔚敏《数据结构（C 语言版）》3.4 广义表的长度与深度、王道《数据结构》广义表章节练习。
广义表 LS = (a₁, a₂, …, aₙ) 的每个元素 aᵢ 既可以是原子，也可以又是一个广义表。长度与深度是它最容易混淆的两个量：长度只数最外层有多少个元素，深度看括号的重数。本题在长度之外还要数两个递归量——全表一共包含多少个原子、一共出现了多少个内部表结点。这三个计数都只依赖括号表示，一遍扫描即可算出，但必须分清“顶层”与“全表递归”两种口径。
题目
广义表的括号表示
教材记法约定：
- 原子是单个字母或单个数字；
- 元素之间用逗号分隔；
- 表用一对括号包起来，括号可以任意嵌套；
- 空表写成
()； - 输入不含空白字符，且保证最外层是括号。
三个计数量的定义（冻结）
- 长度 = 顶层元素个数（原子和子表都算一个元素，只数最外层，不递归）。
- 原子总数 = 全表递归所有原子的个数。
- 子表总数 = 全表内部作为元素出现的表结点数，不含最外层整表；作为元素出现的空表
()计1个；当整个输入就是()时，因它没有内部元素，输出0。
任务要求
- 从标准输入读入一行广义表；
- 输出一行三个整数
长度 原子总数 子表总数； - 三个整数用单个空格分隔，行末无多余空格。
输入格式
- 一行：广义表（原子为单个字母或数字；逗号分隔；括号嵌套；允许空表
()；不含空白字符；保证最外层是括号）。
输出格式
- 一行三个整数：长度、原子总数、子表总数。
数据范围与限制
| 项目 | 范围 |
|---|---|
|L|（输入长度） | 1 ≤ |L| ≤ 10⁵ |
| 嵌套深度（括号重数） | ≤ 10³ |
| 时间复杂度 | O(|L|) |
| 空间复杂度 | O(嵌套深度)，建议用显式栈 |
样例
冻结样例表
| 输入 | 长度 | 原子 | 子表 |
|---|---|---|---|
() | 0 | 0 | 0 |
(a) | 1 | 1 | 0 |
((a)) | 1 | 1 | 1 |
(a,(b,c),(d,(e))) | 3 | 5 | 3 |
((),(a)) | 2 | 1 | 2 |
(()) | 1 | 0 | 1 |
(a,b,c) | 3 | 3 | 0 |
样例输入 1
(a,(b,c),(d,(e)))样例输出 1
3 5 3样例输入 2
((),(a))样例输出 2
2 1 2样例解释
样例 1：输入是 (a, (b,c), (d,(e)))。
- 长度 3：最外层用逗号隔开三个元素——原子
a、子表(b,c)、子表(d,(e))，所以顶层元素个数是3。注意(e)虽然在最外层括号里面，却是(d,(e))的元素，不算顶层元素。 - 原子 5：全表递归数原子，依次是
a、b、c、d、e，共5个。 - 子表 3：作为元素出现的表结点依次是
(b,c)、(d,(e))、(e)，共3个。最外层整表(a,(b,c),(d,(e)))本身被排除在外。
样例 2：((),(a)) 的最外层有两个元素——空子表 () 和子表 (a)，所以长度是 2；全表只有一个原子 a，原子总数是 1；内部表结点是 () 和 (a)，其中空表 () 作为元素出现要计 1 个，所以子表总数是 2。
为什么 ((a)) 的子表总数是 1 而不是 2？ 输入里一共出现了两对括号：最外层整表，以及作为它唯一元素的子表 (a)。定义明确要求不含最外层整表，所以只有 (a) 这一个内部表结点计入，2 − 1 = 1。同理 (a) 的子表总数是 0，而整个输入就是 () 时连内部元素都没有，输出 0 0 0。
如何验证
先安装 Node.js、pnpm 和支持 C++17 的编译器。GNU Make 是首选入口，但不是强制依赖。
# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make scoreWindows 没有安装 Make 时，在仓库根目录使用完全相同的评分内核：
pnpm lab:doctor -- labs/chapter-03/exercise/E-03-15-generalized-list-length
pnpm lab:run -- labs/chapter-03/exercise/E-03-15-generalized-list-length
pnpm lab:score -- labs/chapter-03/exercise/E-03-15-generalized-list-length思考题
- 广义表的长度与深度分别刻画了什么？
(a)和((a))的长度相同，它们的差别体现在哪个量上？ - 为什么“子表总数”要排除最外层整表？如果不排除，
()的结果会变成什么？ - 递归求子表总数在深度 10³ 时有什么风险？显式栈解法把哪部分信息从调用栈搬到了堆上？
- 若允许共享子表（如
E = (a, E)的递归引用），“子表总数”还应该是现在这个定义吗？需要怎样补充约定？
题解
点击查看题解
思路
一遍扫描括号表示，用一个显式栈维护“每个已经打开的表当前数到了多少个顶层元素”：
- 遇到
(：新开一张表。如果此时栈非空，说明这张表是上一层表内部的元素，于是子表总数 +1，并把父表的元素计数+1；然后把新表的计数器0压栈。 - 遇到原子：原子总数 +1；栈非空时把父表的元素计数
+1。 - 遇到
)：弹栈。如果弹空，说明刚刚结束的是最外层整表，它的元素计数就是长度。 - 遇到
,：只是元素分隔符，不参与任何计数。
因为输入保证最外层是括号且一定合法，扫描结束时栈必然恰好清空一次，长度只在这一刻被赋值。
复杂度分析
每个字符只处理一次，时间复杂度 O(|L|)；栈的深度等于当前括号层数，空间复杂度 O(嵌套深度)，最大 10³。如果用递归下降解析，调用栈同样深 10³，虽然本题勉强能过，但显式栈把深度信息放到堆上，不依赖编译器的栈大小，是更稳的写法。
边界注意
- 整个输入就是
()：没有内部元素，输出0 0 0； - 作为元素出现的空表
()：计 1 个子表，不贡献原子，但会把父表的元素计数+1； (a)：只有最外层整表一对括号，子表总数是0；((a))：两对括号，减去最外层整表，子表总数是1；- 数字原子与字母原子同等对待，都是 1 个原子；
- 纯平表（没有子表）的原子总数等于长度，子表总数为
0； - 计数用
long long，长度可达 10⁵，不会溢出但保持口径统一。
参考代码
#include <iostream>
#include <string>
#include <vector>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string text;
std::getline(std::cin, text);
std::vector<long long> elementCount; // 每个已打开表的顶层元素计数
long long length = 0; // 长度：顶层元素个数
long long atoms = 0; // 原子总数
long long subTables = 0; // 子表总数：不含最外层整表
for (char ch : text) {
if (ch == '(') {
if (!elementCount.empty()) { // 这张表作为元素出现在上一层表内部
++subTables;
++elementCount.back();
}
elementCount.push_back(0);
} else if (ch == ')') {
const long long elements = elementCount.back();
elementCount.pop_back();
if (elementCount.empty()) length = elements; // 最外层整表结束
} else if (ch == ',') {
continue; // 元素分隔符不参与计数
} else if (ch == '\r' || ch == '\n' || ch == ' ' || ch == '\t') {
continue; // 输入约定不含空白，这里只做换行符的容错
} else {
++atoms;
++elementCount.back();
}
}
std::cout << length << ' ' << atoms << ' ' << subTables << '\n';
return 0;
}