「省选联考 2022 Day1」预处理器

#题面

#题目描述

宏是 C/C++ 语言的一项特性，它根据预先定义的规则进行文本替换（也被称为 “宏展开”），能够实现定义常量、简化代码重复输入等功能。例如：

C++

1 2	`#define PI 3.14159 double area = PI * r * r;`

以上代码经过宏展开后变为：

C++

1 2	`double area = 3.14159 * r * r;`

其中，宏定义命令变成了空行，而其他行中的宏被展开成了规则定义的文本。

C/C++ 语言代码在编译时对宏的处理由预处理器完成。你的任务是实现一个简化版的预处理器，要求如下：

代码由行组成，每行除行末的换行符外，均由可打印 ASCII 字符（ASCII 码范围 $32\sim 126$ ）组成。每行要么是 预处理命令（以 # 开头），要么是 普通文本（其他情况）。
预处理器逐行处理代码，
- 如果是预处理命令，执行该命令，并输出一个空行。
- 如果是普通文本，对其进行宏展开并输出结果。
预处理命令有两种，分别是宏定义命令 #define 和取消宏定义命令 #undef。
- 宏定义命令的格式为 #define <name> <content>，其中第一部分 #define 是命令名，第二部分 <name> 是要定义的宏的名字，第三部分 <content> 是要定义的宏的展开内容。
- 取消宏定义命令的格式为 #undef <name>，其中第一部分 #undef 是命令名，第二部分 <name> 是要取消的宏的名字。
以上两种预处理命令中，相邻两部分之间都严格用一个空格分隔。<name> 是由大小写字母和数字以及下划线组成的标识符（一个或多个字符），<content> 可以包含任意可打印 ASCII 字符（零个或多个字符）。一个宏定义的有效范围是从它定义所在行开始到后续最近的宏名匹配的取消定义所在行为止（如果没有对应的取消定义，则有效范围一直覆盖到文件结束）。

对普通文本进行宏展开时，将一行文本中每段连续极长的大小写字母和数字以及下划线视为标识符（而不是其中一部分），其余为其他字符。从左到右依次对文本中的标识符进行宏展开：

如果该标识符是有效的宏名，则用对应的展开内容替换它，此时该宏名进入正在展开的状态，直到本流程结束；否则原样保留宏名。例如，若宏 A 定义为 b，则文本 A 展开结果为 b（发生替换），文本 B 展开结果仍然为 B（未定义，不替换），文本 AA 展开结果仍然为 AA（AA 是不同于 A 的另一个标识符，未定义），而文本 A*B 展开结果为 b*B。
替换发生后，如果展开内容中包含标识符，重复应用以上的展开操作，称为 “多次展开”。例如，若宏 A 定义为 B，宏 B 定义为 c，则文本 A 的展开结果为 c。
如果待展开的宏名与正在进行展开的某个宏名相同，称为 “递归展开”，此时该宏名不再展开。本规则用来防止无限递归展开。例如，若宏 A 定义为 B+a，宏 B 定义为 A+b，则文本 A 展开结果为 A+b+a，由于最初的 A 处于正在展开状态，因此 A+b+a 里的 A 不再展开。
其他字符原样保留。

注意：出于简化的目的，本题的要求与 C/C++ 语言标准里的描述不完全一致，请以上面的要求为准。最明显的区别是本题只有标识符和其他字符两类词法单元，没有数值、字符串、注释等。

#输入格式

输入的第一行包含一个正整数 $n$ ，表示要处理的代码行数。

接下来的 $n$ 行是要处理的代码。

#输出格式

输出 $n$ 行，为输入逐行预处理后的结果。

#输入输出样例

输入样例 #1

C++

5
#define BEGIN {
#define END }
#define INTEGER int
class C BEGIN INTEGER x; END;
INTEGER main() BEGIN C c; END

样例输出 #1

C++




class C { int x; };
int main() { C c; }

样例输入 #2

见附件中的 preprocessor/preprocessor2.in。

样例输入 #2

见附件中的 preprocessor/preprocessor2.ans。

样例输入 #3

见附件中的 preprocessor/preprocessor3.in。

样例输入 #3

见附件中的 preprocessor/preprocessor3.ans。

#数据范围与约定

【数据范围】

对 $20\%$ 的数据，不会出现宏定义命令 #define 和宏取消定义命令 #undef。

对另外 $20\%$ 的数据，不会出现多次展开的情况，且不会出现宏取消定义命令 #undef。

对另外 $20\%$ 的数据，不会出现多次展开的情况。

对另外 $20\%$ 的数据，不会出现递归展开的情况。

对其余数据，无特殊限制。

对 $100\%$ 的数据， $n \leq 100$ ，输入的每行字符数都不超过 $100$ ，且保证输出的每行字符数都不超过 $1000$ （字符数均不计行末换行符）。保证输入数据中的预处理命令都是合法的，包含但不限于：

# 字符只会出现在预处理命令所在行的第一个字符的位置，其他任何位置（包括预处理命令和普通文本）都不会出现 # 字符。
宏定义和取消定义命令的格式是正确的，严格遵循题面所描述的格式。
同一个宏在取消定义之前不会被再次定义。
要取消定义的宏在之前被定义过且还没有被取消过。

也就是说，你不需要做任何语法和语义的错误检查。

【提示】

本题进行输入时建议使用 C++ 语言的按行读入字符串功能，示例如下：

C++

#include <iostream>
#include <string>
using namespace std;
string line;
// 从 cin 读入一行，放入 line 中（换行符被舍弃）
getline(cin, line);

也可以使用 C 语言提供的 fgets 函数，示例如下：

C++

#include <stdio.h>
#define MAX_LEN 200
char line[MAX_LEN];
// 从 stdin 读入一行，放入 line 中（包含换行符）
fgets(line, MAX_LEN, stdin);

注意：在读取行数 $n$ 之后可能需要额外读取一行以忽略其后的换行符。

#思路

这是一道不大不小的模拟题，有一些注意事项：

判断有效的宏名（正则：[A-Za-z0-9_]+）比判断分隔符要容易实现。
题目有要求不能展开无限递归的宏，需要打标记记录一下。
STL 是个好东西。

题外话：我在省选前不久碰见了一个短小精悍的 C 语言编译器，而里面正好有预处理相关的代码：preprocess.c at rui314/chibicc@90d1f7f。可惜的是，这么长的代码我记不住，而且过于工程化，没有必要在考场上写这种东西。不过这个编译器和我曾经用到的 PurgeCSS 库为我提供了一些思路和实现上的点拨，使得我能在考场上切掉这道题，写出来的代码也不至于特别冗长。

#STL 相关

一个非常好用的 C++ 参考手册（中文）：zh.cppreference.com。

在考场上如果不知道怎么用 STL 可以去翻头文件中的注释（英文），里面有简单的说明。

#`std::string` 入门

声明一个 std::string 类型的变量 s：

C++

1	`std::string s = "abcdef";`

获取字符串长度：

C++

1 2	`s.size(); // 6`

判空：

C++

1 2	`s.empty(); // false`

截取子串：

C++

1 2	`s.substr(1, 3); // s 中从 1 开始长度为 3 的子串 // "bcd"`

查找字串：

C++

1 2	`s.find("cde", 1); // s 中从下标为 1 的位置开始查找字串 "cde" // 2`

同样地，也可以查找某个字符出现的位置：

C++

1 2	`s.find('c'); // s 中第一次出现的 'c' // 2`

STL 也提供了其他查找函数：

find_first_of：查找字符串中第一个包含指定字符的位置。
find_last_of：查找字符串中最后一个包含指定字符的位置。
find_first_not_of：查找字符串中第一个不包含指定字符的位置。
find_last_not_of：查找字符串中最后一个不包含指定字符的位置。

使用方法与上面的 find 函数类似，不再过多赘述。

清空字符串：

C++

1	`s.clear();`

#`std::unordered_map` 入门

std::unordered_map 在 C++11 中被引入，由于其基于哈希的实现导致了在大多数情况下 std::unordered_map 比 std::map 要快。

声明一个 std::unordered_map<std::string, int> 类型的变量 map：

C++

1	`std::unordered_map<std::string, int> map;`

插入元素：

C++

1
2
3

map["a"] = 1;
map.insert(std::make_pair("b", 2));  // pair 的 first 键值为 key，second 键值为 value
map["c"] = -1;

查找元素：

C++

1 2	`map.find("c"); // 返回迭代器 map.count("c"); // 返回元素个数（1 或 0）`

删除迭代器 it 指向的元素：

C++

1 2	`auto it = map.find("c"); map.erase(it);`

删除键为 c 的元素：

C++

1	`map.erase("c");`

获取元素个数：

C++

1 2	`map.size(); // 2`

判空：

C++

1 2	`map.empty(); // false`

访问元素：

C++

1 2	`map["a"]; // 1`

使用下标访问时如果元素不存在会自动新建，所以建议访问前先使用 map.count() 判断是否存在该元素。

清空整个容器：

C++

1	`map.clear();`

#代码

C++

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

// 题目限制
const int N = 105;

// 代码行数
int n;
// 原始字符串
std::string s[N];
// 宏列表：        <宏名,                 <内容,     正在展开>>
std::unordered_map<std::string, std::pair<std::string, bool>> def;

/**
 * 递归展开
 * @param s 原始字符串
 * @return 展开后的字符串
 */
std::string dfs(std::string s) {
    std::string r;

    for (int i = 0, j; i < s.size(); i += j) {
        for (j = 0; i + j < s.size() &&                     // 防止越界
                    ('0' <= s[i + j] && s[i + j] <= '9' ||  // 数字
                     'a' <= s[i + j] && s[i + j] <= 'z' ||  // 小写字母
                     'A' <= s[i + j] && s[i + j] <= 'Z' ||  // 大写字母
                     s[i + j] == '_');                      // 下划线
             j++)
            ;  // 匹配合法宏名

        if (j) {
            std::string tmp = s.substr(i, j);  // 截取从 i 开始的 j 个字符

            if (def.count(tmp) && !def[tmp].second) {  // 该宏存在且未处在展开状态
                def[tmp].second = true;                // 将该宏标记为正在展开
                r += dfs(def[tmp].first);              // 递归展开
                def[tmp].second = false;               // 取消标记
            } else {
                r += tmp;  // 不存在直接按原样加入到结果中
            }
        } else {
            r += s[i++];  // 不合法，直接略过，加入到结果中
        }
    }

    return r;
}

int main() {
    std::ios::sync_with_stdio(false);

    cin >> n;

    // 第 0 行读入 n 后尾随的换行符
    for (int i = 0; i <= n; i++) {
        std::getline(cin, s[i]);
    }

    for (int i = 1; i <= n; i++) {
        if (s[i][0] == '#') {  // 预处理命令
            if (s[i].substr(1, 6) == "define") {
                int p = s[i].find_first_of(' ', 8);  // 宏名后的空格位置

                std::string name = s[i].substr(8, p - 8),
                            content = s[i].substr(p + 1);

                // 插入内容
                def[name] = std::make_pair(content, false);
            } else {  // s[i].substr(1, 6) == "undef"
                std::string name = s[i].substr(7);
                def.erase(name);
            }
            cout << endl;
        } else {  // 普通文本
            cout << dfs(s[i]) << endl;
        }
    }

    return 0;
}

时间限制	1s
内存限制	512MB
文件 I/O	输入：`preprocessor.in` 输出：`preprocessor.out`
题目难度	普及+/提高
提交地址	洛谷 LibreOJ
题目来源	联合省选 2022