P8289题解
__vector__ · · 题解
前言：
这道题是省选的签到题，然而我交了很多遍才 AC
题目注意事项：
-
#define <name> <content>中的content可以为空 -
连续在一起的大小写字母和数字以及下划线应该视作同一个标识符
题目做法：
读入：
这里的读入有亿些坑，在此说一下
读入 getchar 来吸收换行符，不然会挂。
读入每一行的字符串时，可以这样读入：
fgets(line, maxn, stdin);
//line是临时存储每一行字符串的char数组
//maxn是数组大小至于如何读入宏，首先可以使用 sscanf 从 line 数组将开头的 #define 或 #undef，以及宏名读入，具体如下：
sscanf(line,"%s%s",define.tmp,define.name);
//define.tmp 是 "#define" 或 "#undef"
//define.name 是宏名最后的宏的内容，也就是 content，应该从预处理指令的前两个单词的末尾的向后两个位置开始依次一个一个的读入每个字符。具体如下：
for(int i=ttmp,cnt=0;i<size_line;i++,cnt++)
{
if(line[i]=='\n')break;
define.val[cnt]=line[i];
//define.val 是宏的内容(content)
//ttmp 是预处理命令的前两个单词的末尾的向后两个位置
//也就是预处理命令第三个单词开始的位置
//size_line 是 line数组的大小
}之所以不能直接读入是因为宏的内容 content 可以为空。
宏的存储
因为 map 的复杂度是 unordered_map，这样复杂度是 map 用的是红黑树，unordered_map 用的是哈希表。
定义一个 unordered_map 来存储每个宏名替换之后的内容：
unordered_map<string,string> def;然后 def[name]=content 就行了
宏的展开
注：line 数组是临时存储每一行字符串的。此时 string ans 用来存储答案。
遍历 line 数组，按照题目要求找标识符。找到一个标识符，首先判断它是不是一个有效的宏名，如果不是，那么 ans 直接加上这个标识符即可，如果它是一个有效的宏名，那么对其进行展开之后 ans 再加上它，下面来说一下如何进行展开。
因为一个宏展开之后可能还需要继续展开，这样就很麻烦，使用 dfs 可以方便的进行递归展开。来说一下怎么 dfs：
定义：string dfs(string hong)
其中 dfs 的返回值是宏展开之后的字符串，hong 是待展开的宏名。
递归到某个宏，首先把这个宏变成这个宏第一次展开之后的字符串，也就是 hong = def[hong]，并定义一个临时数组 string str 来存储当前宏完全展开之后的最终字符串，遍历 hong 数组，查找每一个标识符，如果这个标识符 name 是一个有效的宏名，那么对其 dfs 递归展开：str+=dfs(name)，否则直接加入 str 数组。
最后返回 str 数组。
那么如何处理无线递归展开呢？
可以定义一个 unordered_map<string,bool> vis 来记录当前递归正在展开的宏名，每递归到一个宏名 name，就将这个宏名记录下来：vis[name]=1，如果发现当前宏名与某个正在展开的宏名相同，也就是 if(vis[name]==1)，那么当前宏名不作展开，直接把宏名返回即可。
AC 代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
namespace Main
{
const int maxn=105;
int n;
char line[maxn];
unordered_map<string,string> def;
int size_line;
struct Define
{//用来临时存储正在读入宏的信息
char tmp[10];
char name[maxn];
char val[maxn];
}define;
string ans_line;//存储每个蒲通文本宏展开后的样子
string temp;
unordered_map<string,bool> vis;
bool isletter(char s)
{
if(isdigit(s))return 1;
if(s=='_')return 1;//注意数字和下划线与字母一起组成标识符
if(s-'a'>=0&&s-'a'<26)return 1;
if(s-'A'>=0&&s-'A'<26)return 1;
return 0;
}
string dfs(string hong)
{
string ttttmp=hong;//临时存储原来的宏名
hong=def[hong];//把hong 变成其一次展开后的样子
if(vis[ttttmp])return ttttmp;
//如果与正在进行展开的某个宏名相同，返回
vis[ttttmp]=1;
string str="";
string temp="";//存标识符
for(int i=0;i<hong.size();i++)
{
if(hong[i]=='\n')break;
// cout<<"temp: "<<temp<<endl;
if(isletter(hong[i]))
{
temp+=hong[i];
}
else
{
if(def.count(temp))
{//连续字母结束，处理一下宏
//不要忘记读入完整个字符串之后还要展开一下temp
str+=dfs(temp);
}
else
{
str+=temp;
}
temp=hong[i];
if(def.count(temp))
{//如果当前文本是一个宏，替换一下
str+=dfs(temp);
}
else
{//不是宏，不做处理
str+=temp;
}
temp="";
}
}
if(def.count(temp))
{
str+=dfs(temp);
}
else
{
str+=temp;
}
vis[ttttmp]=0;
return str;
}
void main()
{
cin>>n;
getchar();
while(n--)
{
fgets(line, maxn, stdin);
size_line=strlen(line);
if(line[0]=='#')
{//预处理指令
sscanf(line,"%s%s",define.tmp,define.name);
int ttmp=strlen(define.tmp)+strlen(define.name)+2;
memset(define.val,0,sizeof(define.val));
for(int i=ttmp,cnt=0;i<size_line;i++,cnt++)
{
if(line[i]=='\n')break;
define.val[cnt]=line[i];
}
if(define.tmp[1]=='d')
{
def[define.name]=define.val;
}
if(define.tmp[1]=='u')
def.erase(define.name);//#undef
putchar('\n');
continue;
}
else
{//蒲通文本
ans_line="";
temp="";
for(int i=0;i<size_line;i++)
{
if(line[i]=='\n')break;
// cout<<"temp: "<<temp<<endl;
if(isletter(line[i]))
{
temp+=line[i];
}
else
{
if(def.count(temp))
{//连续字母结束，处理一下宏
//不要忘记读入完整个字符串之后还要展开一下temp
ans_line+=dfs(temp);
}
else
{
ans_line+=temp;
}
temp=line[i];
if(def.count(temp))
{//如果当前文本是一个宏，替换一下
ans_line+=dfs(temp);
}
else
{//不是宏，不做处理
ans_line+=temp;
}
temp="";
}
}
if(def.count(temp))
{
ans_line+=dfs(temp);
}
else
{
ans_line+=temp;
}
cout<<ans_line<<endl;
}
}
}
}
int main()
{
Main::main();
return 0;
}