题目重点：解析 Ethernet(1-3)/(1-4) 这类表达式，按题目次序展开数字范围和枚举选项，处理输出爆炸、非法括号与复杂度。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练语法：普通文本原样保留；括号内是逗号分隔的字面选项，或两个非负十进制整数 a-b 形成闭区间。
- 括号不嵌套；未定义转义符和字面括号。空括号、空枚举项、递减范围与不匹配括号被视为非法输入。
- 顺序按左到右笛卡儿积：先固定左组选项，再遍历右组选项；重复选项是否去重题目未说，训练版保留。
- 返回全部展开字符串，设置 max_outputs 保护内存；真实接口如允许迭代器可改为惰性生成。
解题路线
- 从左到右扫描。遇普通文本就找到下一个左括号，将整段 literal 追加到当前每个部分结果末尾；遇左括号就定位对应右括号并解析内部选项。
- 维护 result 初始为 ['']；若解析出 choices，对每个已有 prefix 按 choices 顺序生成 prefix+choice。这正是逐组笛卡儿积。
- 解析 '-' 时只在整组恰好为两个数字端点且无逗号时当作范围；逗号分隔是字面枚举，避免把 pt1 误当数字。
- 在分配前计算 |result|×|choices| 并检查输出上限；若范围特别大，解析器可用惰性 range，避免先物化所有 choices。
手动走一遍
Ethernet(1-3)/(1-4)：首组变为 Ethernet1、Ethernet2、Ethernet3；加斜杠后再与 1..4 做积，先输出 Ethernet1/1..4，再 Ethernet2/1..4，最后 Ethernet3/1..4。第二个枚举样例的 e 是普通文本，因此 Ethernet1ept1 等自然得到。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Training grammar: literal text and non-nested (a,b,1-3) groups."""
def expand(pattern: str, max_outputs: int = 100_000) -> list[str]:
if max_outputs < 0:
raise ValueError("negative output limit")
result = [""]
i = 0
while i < len(pattern):
if pattern[i] == ")":
raise ValueError("unmatched closing parenthesis")
if pattern[i] != "(":
end = pattern.find("(", i)
if end < 0:
end = len(pattern)
literal = pattern[i:end]
if ")" in literal:
raise ValueError("unmatched closing parenthesis")
result = [prefix + literal for prefix in result]
i = end
continue
end = pattern.find(")", i + 1)
if end < 0 or "(" in pattern[i + 1:end]:
raise ValueError("missing close or nested group")
body = pattern[i + 1:end]
if not body:
raise ValueError("empty group")
if "," in body:
choices = body.split(",")
if any(not item for item in choices):
raise ValueError("empty option")
elif "-" in body:
parts = body.split("-")
if len(parts) != 2 or not all(part.isdecimal() for part in parts):
raise ValueError("invalid integer range")
lo, hi = map(int, parts)
if lo > hi:
raise ValueError("decreasing range")
choices = [str(number) for number in range(lo, hi + 1)]
else:
choices = [body]
if len(result) * len(choices) > max_outputs:
raise ValueError("output limit exceeded")
result = [prefix + option for prefix in result for option in choices]
i = end + 1
return result
if __name__ == "__main__":
assert expand("Ethernet(1-3)/(1-4)")[:4] == [
"Ethernet1/1", "Ethernet1/2", "Ethernet1/3", "Ethernet1/4"]
复杂度
设输入长 L、最终输出数 P、输出字符总数 C。扫描括号与正文 O(L)，逐阶段字符串拼接时间和空间与中间/最终输出字符量有关，最坏 O(C×组数) 的重复前缀拷贝；至少需要 Ω(C) 来返回全部结果。P 是各组选项数的乘积，可呈指数增长，max_outputs 只是工程保护，不改变理论上界。
易错点与追问
容易失分的边界
- 用一个贪婪正则一次性吞掉多个括号，丢失分组边界。
- 将所有括号选项拼在一起而没有做笛卡儿积。
- 枚举 (pt1,ptb) 中的字母被错误当范围，或 (1-3) 被当字符串 '1-3'。
- 声称算法严格线性于输入长度，忽略输出规模可能指数级。
- 题目未说支持嵌套，不应声称此实现是完整通用表达式解析器。
继续深挖
- 若允许嵌套括号和转义字符，需要怎样的递归下降语法？
- 若输出数量巨大，如何设计 generator 与分页游标？
- 如何在不生成全部字符串时求第 k 个展开值？
