问题分析

我们需要实现一个简化的 C/C++ 预处理器，主要功能是处理宏定义和宏展开。

核心机制：

• 维护一个宏表，记录当前有效的宏定义
• 处理两种预处理指令：#define 和 #undef
• 对普通文本进行递归宏展开，同时防止无限递归

---

关键规则理解

1. 宏的作用域

• 从 #define 所在行开始生效
• 到对应的 #undef 所在行结束（如果没有 #undef 则持续到文件末尾）
• 这是一个动态作用域，需要逐行更新宏表

2. 标识符识别

• 标识符：连续的字母、数字、下划线
• 其他字符：非标识符字符，原样保留
• 关键：AA 和 A 是不同的标识符

3. 展开规则

1. 基本展开：遇到标识符，如果在宏表中，就替换为对应内容
2. 多次展开：替换后的内容如果包含标识符，继续展开
3. 防递归：如果某个宏名正在展开过程中，再次遇到时不展开

---

算法设计

1. 总体流程

初始化空的宏表
对于每一行代码：
    if 以'#'开头：
        执行预处理命令
        输出空行
    else：
        进行宏展开
        输出展开结果

2. 预处理命令处理

• #define name content：将 (name → content) 加入宏表
• #undef name：从宏表中删除 name

3. 宏展开算法（核心）

递归展开函数 expand(text, expanding_set)：

• 输入：待展开文本 + 当前正在展开的宏名集合
• 输出：展开后的文本

步骤：

1. 扫描文本，分离出标识符和其他字符
2. 对于每个标识符：
   • 如果它在 expanding_set 中：原样保留（防递归）
   • 否则如果在宏表中：
     • 将其加入 expanding_set
     • 递归展开其定义内容：expand(content, expanding_set)
     • 将其移出 expanding_set
   • 否则：原样保留
3. 拼接所有部分作为结果

---

示例分析

样例1的展开过程

宏表：BEGIN→{, END→}, INTEGER→int

文本：class C BEGIN INTEGER x; END;
扫描：
- "class", "C"：未定义，保留
- "BEGIN"：展开为"{"
- "INTEGER"：展开为"int"  
- "x"：未定义，保留
- "END"：展开为"}"
结果：class C { int x; };

递归展开示例

宏定义：A→B, B→c
文本：A
展开过程：
1. A在宏表中 → 展开为B（A加入expanding_set）
2. B在宏表中 → 展开为c（B加入expanding_set）  
3. c不在宏表 → 返回c
最终结果：c

防递归示例

宏定义：A→B+a, B→A+b
文本：A
展开过程：
1. A → 展开B+a（A加入expanding_set）
2. B → 展开A+b（B加入expanding_set）
3. 遇到A，但A在expanding_set中 → 保留A
结果：A+b+a

---

实现细节

1. 数据结构选择

• 宏表：unordered_map<string, string>
• 正在展开集合：unordered_set<string>

2. 标识符识别

遍历字符串，根据字符类型判断：

• 字母/数字/下划线：标识符部分
• 其他：分隔符

3. 递归控制

通过 expanding_set 参数传递当前展开路径，防止循环：

def expand(text, expanding):
    result = []
    while 有标识符：
        if 标识符在expanding中：
            原样输出
        elif 标识符在宏表中：
            expanding.add(标识符)
            content = expand(宏定义, expanding)
            expanding.remove(标识符)
            result.append(content)
        else：
            原样输出
    return 拼接结果

---

复杂度分析

• 时间复杂度：最坏情况 $O(n × L × D)$
  • $n$：行数
  • $L$：每行长度
  • $D$：递归深度
• 空间复杂度：$O(M + D)$
  • $M$：宏表大小
  • $D$：递归深度

由于数据限制严格（$n ≤ 100$，每行 ≤ 100 字符），完全可行。

---

总结

这道题考察的是：

1. 对复杂规则的理解和实现能力
2. 递归算法的设计和控制
3. 字符串处理的精确性
4. 状态管理的正确性

关键难点：

• 正确处理递归展开和防循环机制
• 准确识别标识符边界
• 动态维护宏的作用域

通过仔细分析规则，设计合适的递归算法，并注意边界情况，就能正确实现这个预处理器。