「联合省选 2022」预处理器 - 模拟

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

对于该题，你需要展开 #define 宏定义。本题中的宏定义与 C++ 中的宏定义大致相同，不过有下列特点：

  • 可以用 #undef 取消宏定义；
  • 可以进行多次展开。如 #define a b+e，#define b c+d，对于 a 最终展开结果为 c+d+e；
  • 可以进行递归展开，但若待展开的宏名与正在进行展开的某个宏名相同，为了防止无限递归，此时宏名就不再展开。如 #define a b+c，#define b a+a，对于 b 的展开结果即为 b+c+b+c。

其他细节详见题面。

解题思路

一道让 OI 倒退 15 年的题

本题是一道细节超多的模拟题。

首先我们需要解决这道题的输入。以分隔符为界，分段读入即可。每个分隔符（包括空格）可以看成单独一个字符串读入即可。

然后我们可以用 std::map<std::string, std::string> 存储 #define 的对应关系。对于 #undef，我们仅需在 map 中删除该项即可。

最后我们需要解决的是字符串展开问题，也是本题中细节最多的部分。

由于本题中涉及了递归展开，我们可以考虑使用递归来编写处理函数 solve。首先考虑在 map 中是否有已经定义的字符串或者是否被打标记，若 map 中没有或被打了标记则直接输出。若有，则进行以下操作：

  1. 进行标记（在本代码中使用 vis 进行）；
  2. 展开当前的字符串；
  3. 将字符串分段读入（读入方式见上）；
  4. 对于每段字符串分别递归求解；
  5. 取消标记。

注意 4 步很重要，若直接展开后递归，则无法处理两将要展开的字符串并列的情况。接下来为该情况 Hack 数据：

1
2
3
4
3
#define a b+c
#define b a+a
b

结果应为 b+c+b+c，但是直接展开后递归的结果会是 b+c+a。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <cstdio>
#include <iostream>
#include <string>
#include <tuple>
#include <map>
#include <vector>

std::map<std::string, std::string> def;
std::map<std::string, bool> vis;

inline bool isID(char ch) {
    if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9') || ch == '_') return true;
    else return false;
}

// tuple 中第一项代表读到的字符串，第二项表示是否为分隔符，第三项表示结束位置对应 src 的下标
// 建议可以学一下 tuple 的用法
inline std::tuple<std::string, bool, int> reads(std::string src, int pos) {
    if (isID(src[pos])) {
        std::string str = "";
        int len = src.length();
        while (pos < len && isID(src[pos])) {
            str += src.substr(pos, 1);
            pos++;
        }
        return std::make_tuple(str, true, pos);
    } else {
        std::string str = "";
        str += src.substr(pos, 1);
        return std::make_tuple(str, false, pos + 1);
    }
}

// 这个函数专门读 #define
inline std::pair<std::string, int> readDef(std::string src, int pos) {
    int len = src.length();
    while (pos < len && isspace(src[pos])) pos++;
    std::string str = "";
    while (pos < len && !isspace(src[pos])) str += src[pos++];
    return std::make_pair(str, pos);
}

void solve(std::string str) {
    if (def.count(str) != 0 && !vis[str]) {
        vis[str] = true;
        std::string src = str;  // 注意要存原先字符串以在取消标记时使用
        str = def[str];
        std::tuple<std::string, bool, int> getReads = std::make_tuple("", true, 0);
        int len = str.length();
        std::vector<std::string> vec;
        while (std::get<2>(getReads) < len) {
            getReads = reads(str, std::get<2>(getReads));
            vec.push_back(std::get<0>(getReads));
        }
        for (std::string each : vec) solve(each);
        vis[src] = false;
    } else std::cout << str;
}

int main() {
    std::cin.tie(0);
    std::cout.tie(0);

#ifndef XEDEBUG
    freopen("preprocessor.in", "r", stdin);
    freopen("preprocessor.out", "w", stdout);
#endif

    int n;

    std::cin >> n;
    std::cin.ignore();

    for (int i = 1; i <= n; i++) {
        std::string str;
        std::getline(std::cin, str);
        std::tuple<std::string, bool, int> getReads = std::make_tuple("", true, 0);
        int len = str.length();

        while (std::get<2>(getReads) < len) {
            getReads = reads(str, std::get<2>(getReads));

            if (std::get<1>(getReads)) {
                vis.clear();
                for (auto each : def) vis[each.first] = false;
                solve(std::get<0>(getReads));
            } else if (std::get<0>(getReads) == "#") {
                getReads = reads(str, std::get<2>(getReads));
                if (std::get<0>(getReads) == "define") {
                    std::pair<std::string, int> from = readDef(str, std::get<2>(getReads));
                    std::string to = str.substr(from.second + 1);
                    def[from.first] = to;
                    getReads = std::make_tuple(to, true, len);
                } else if (std::get<0>(getReads) == "undef") {
                    std::string from = str.substr(std::get<2>(getReads) + 1);
                    def.erase(from);
                    getReads = std::make_tuple(from, true, len);
                } else {
                    std::cout << "#";
                    getReads = std::make_tuple("#", false, std::get<2>(getReads) + 1);
                }
            } else std::cout << std::get<0>(getReads);
        }

        std::cout << "\n";
    }

#ifndef XEDEBUG
    fclose(stdin);
    fclose(stdout);
#endif

    return 0;
}