题解 P4911【河童重工的计算机】

题目传送门

题意简述

• 给出一段汇编语言。
• 给出输入。
• 求这段汇编语言的输出。

以下还有一些题面中没有强调的要点：

1. 每行只有一条语句；
2. call <0>; 命令会将下一行的序号 $nxt$ 与当前的寄存器 %Line 的值 $line$ 压入栈中；
3. ret <0>; 命令会从栈中取出 $nxt$ 和 $line$，并使程序跳转到第 $nxt$ 行，同时将当前的 %Line 赋值为 $line$；
4. 逗号等于空格；
5. 内存的地址是一个十进制的数字，从0开始；
6. 关键字全是小写，但函数名不一定；
7. 注释可以嵌套；
8. 数据非常简单，不用考虑那些奇奇怪怪的情况。

题目分析

显而易见的，本题是个大模拟题。

先铺垫 c++ 的几个不常用（？）的特性：

• 在定义函数时，如 int function(int f=1)，这里的 f=1 表示「默认」。当我给该函数参数时，f 的默认取值 1 会被覆盖，若我不给参数，则 f 会取默认值。
• 如果定义了变量 a ，则 *a 可以理解为「指向 a 的指针」。
• sscanf() 可以从字符串中读取数据。

本题思维难度不大，其难度主要体现在实现以及码量上。

读懂了题目，那么接下来我们就可以快乐地给汇编语言写解释器了。

题面中提到了一套完整的内存系统，唯有先将它实现好了，才能继续进行工作。

地址系统

考虑如何实现寄存器和内存…啊不用考虑，太简单了，直接开几个变量和一个数组就行了。

但是内存系统的难点就在处理那些字符串上。

既然题干中指令会对内存甚至是常量进行读写，那我们直接获取指针就好了。

因此，我们可以考虑实现一个函数 int*get_address(string address)。

• 对于寄存器和固定位置的内存（“%” 与 “@”），我们直接返回其指针。
• 对于在寄存器值位置的内存（“@%”），我们先获取该寄存器的值，再返回对应位置内存的指针。
• 对于编译时常量与普通常量（“#” 与数字），考虑到命令会对常量进行修改，所以我们可以定义一个变量，赋上常量的值，然后返回该变量的指针。

然后就写好了：

int R1,R2,R3,R4; //寄存器
int E1,E2,E3,E4; //寄存器
int Flag,Val,Ret,Line; //寄存器 
int memory[20000000]; //内存 
int undefine; //对常量的修改 
struct node{
    int nxtline,Line;
    node(int nn,int ll){
        nxtline=nn,Line=ll;
    }
};
stack<node> sAddr; //系统栈 
string code[50005]; //汇编 
int nowline; //当前执行到的行数 

int get_int(string s,bool ch){ //将 字符串/字符 转化为数字
    if(ch) return s[0];
    int res=0;bool neg=0; 
    if(s[0] == '-') neg=1;
    for(int i=(neg?1:0);i<(int)s.size();i++) res=(res<<1)+(res<<3)+(s[i]^48);
    return (neg?-res:res);
}

string get_str(int x){ //将数字转化为字符串
    string res="";
    bool neg=0;
    if(x<0) neg=1,x=-x;
    while(x>0){
        res+=((x%10)^48);
        x/=10;
    }
    reverse(res.begin(),res.end());
    if(neg) return "-"+res;
    return res;
}

int*get_address(string address){
    if(address[0] == '%'){ //寄存器 
        address = address.substr(1);
        if(address == "r1") return&R1;
        if(address == "r2") return&R2;
        if(address == "r3") return&R3;
        if(address == "r4") return&R4;
        if(address == "e1") return&E1;
        if(address == "e2") return&E2;
        if(address == "e3") return&E3;
        if(address == "e4") return&E4;
        if(address == "flag") return&Flag;
        if(address == "val" ) return&Val ;
        if(address == "ret" ) return&Ret ;
        if(address == "line") return&Line;
    }
    if(address[0] == '@'){ //内存 
        if(address.substr(0,2) == "@%") return&memory[*get_address(address.substr(1)  )];
        else                            return&memory[ get_int    (address.substr(1),0)];
        //这种码风可能有人看不惯...凑合着看看吧qaq
    }
    if(address[0] == '#'){ //编译时常量 
        address = address.substr(1);
        if(address == "line"){
            undefine = nowline;
            return&undefine;
        }
    }
    
    if(address[0] == '-' || isdigit(address[0])){//常量 
        undefine=get_int(address,0);
        return&undefine;
    }
    
    return NULL;
}

输入输出

显而易见的，我们可以在读完汇编后停下，在汇编运行时再去读输入输出。

并没有难度。

（read() 就是普通的快读）

namespace output{
    void wint(string address="%val"){
        printf("%d",*get_address(address));
    }
    void wch(string address="%val"){
        printf("%c",*get_address(address));
    }
}

namespace input{
    void rint(string address="%val"){
        *get_address(address)=read(); 
    }
    void rch(string address="%val"){
        string s;cin>>s;
        *get_address(address)=get_int(s,1);
    }
}

运算命令

对着规范文件打就行了，这一部分相对重复。

namespace arithmetic{
    void inv (string a0,          string address="%val" ){*get_address(address) = -(*get_address(a0))                    ;}
    void add (string a0,string a1,string address="%val" ){*get_address(address) =  (*get_address(a0) +  *get_address(a1));}
    void sub (string a0,string a1,string address="%val" ){*get_address(address) =  (*get_address(a0) -  *get_address(a1));}
    void mult(string a0,string a1,string address="%val" ){*get_address(address) =  (*get_address(a0) *  *get_address(a1));}
    void idiv(string a0,string a1,string address="%val" ){*get_address(address) =  (*get_address(a0) /  *get_address(a1));}
    void mod (string a0,string a1,string address="%val" ){*get_address(address) =  (*get_address(a0) %  *get_address(a1));}
    void lsft(string a0,string a1,string address="%val" ){*get_address(address) =  (*get_address(a0) << *get_address(a1));}
    void rsft(string a0,string a1,string address="%val" ){*get_address(address) =  (*get_address(a0) >> *get_address(a1));}
    void band(string a0,string a1,string address="%val" ){*get_address(address) =  (*get_address(a0) &  *get_address(a1));}
    void bor (string a0,string a1,string address="%val" ){*get_address(address) =  (*get_address(a0) |  *get_address(a1));}
    void bxor(string a0,string a1,string address="%val" ){*get_address(address) =  (*get_address(a0) ^  *get_address(a1));}
}

namespace logic{
    void lgr (string a0,string a1,string address="%flag"){*get_address(address) = (bool)(*get_address(a0) >  *get_address(a1));}
    void lls (string a0,string a1,string address="%flag"){*get_address(address) = (bool)(*get_address(a0) <  *get_address(a1));}
    void lge (string a0,string a1,string address="%flag"){*get_address(address) = (bool)(*get_address(a0) >= *get_address(a1));}
    void lle (string a0,string a1,string address="%flag"){*get_address(address) = (bool)(*get_address(a0) <= *get_address(a1));}
    void leql(string a0,string a1,string address="%flag"){*get_address(address) = (bool)(*get_address(a0) == *get_address(a1));}
    void land(string a0,string a1,string address="%flag"){*get_address(address) = (bool)(*get_address(a0) && *get_address(a1));}
    void lor (string a0,string a1,string address="%flag"){*get_address(address) = (bool)(*get_address(a0) || *get_address(a1));}
} 

控制命令

控制命令基本也是对着规范文件打就行了，但是要注意规范文件中的那行小字：
注：JMP、JIF 命令会以 %Line 寄存器为偏移跳转（跳转到相加位置），CALL 命令则不会。

考虑到我的代码的后续实现，这里我往系统栈 sAddr 中压的是当前的 %Line 和当前行的序号，如果后续实现和我不一样一定要看清了。

namespace control{
    void udef(){;}
    void hlt(){exit(0);}
    void nop(){;}
    void set(string a0,string address){
        *get_address(address) = (*get_address(a0));
    }
    void jmp (string a0){
        nowline = (*get_address(a0) + *get_address("%line"));
    }
    void jif (string a0,string a1="%flag"){
        if(*get_address(a1)){
            nowline = (*get_address(a0) + *get_address("%line"));
        }
    }
    void call(string a0){
        sAddr.push(node(nowline,*get_address("%line"))); //跳转之后还会进入下一行，所以这里存储当前行号就行了
        nowline = (*get_address(a0));
    }
    void ret(string a0="%ret"){
        *get_address("%line") = sAddr.top().Line;
        *get_address("%ret") = (*get_address(a0));
        nowline = sAddr.top().nxtline;
        sAddr.pop();
    }
}

预处理

这里的预处理是指删除所有注释以及替换 FUNCTION 命令和 CALLFUNC 命令。

对于注释，可以直接用一些基本字符串操作干掉。

对于 FUNCTION 命令，可以直接用 map 存下该函数的对应行数，然后将原句替换为 set #line %line;。

对于 CALLFUNC 命令，直接在那个 map 里面查到该函数的对应行数，然后将原句替换为 call <对应行数>;。

namespace special{
    map<string,int> end;
    void function(string a0){
        end[a0]=nowline;
    }
    int callfunc(string a0){
        return end[a0];
    }
}

void init(){
    int notes=0;
    for(int i=1;i<=N;i++){ //去注释
        for(string::iterator j=code[i].begin();j!=code[i].end();){
            if((*j) == '[') notes++;
            if((*j) == ']' && notes > 0) notes--;
            
            if((*j) == '[' || (*j) == ']' || notes > 0) code[i].erase(j);
            else j++;
        }
    }
    for(nowline=1;nowline<=N;nowline++){
        int posf=code[nowline].find("function $");
        if(posf != (int)code[nowline].npos){ //没查到
            sscanf(code[nowline].substr(posf+10).c_str(),"%[^;]",subcode); //读取函数名，直到遇到分号
            special::function(subcode); //记录该函数的行数
            code[nowline].erase(posf,10+strlen(subcode)); //删除该语句
            code[nowline].insert(posf,"set #line %line");
        }
    }
    for(nowline=1;nowline<=N;nowline++){
        int posr=code[nowline].find("callfunc $");
        if(posr != (int)code[nowline].npos){ //没查到
            sscanf(code[nowline].substr(posr+10).c_str(),"%[^;]",subcode); //读取函数名，直到遇到分号
            code[nowline].erase(posr,10+strlen(subcode)); //删除该语句
            code[nowline].insert(posr,"call "+get_str(special::callfunc(subcode)));
        }
    }
    return;
}

运行

可以考虑将一条命令分为命令名称和参数两个部分，使用 sscanf() 直接读取名称，然后循环读参数，直到读到分号为止。

然后再根据命令名称去执行。

仍然相当繁琐。

void getcode(){
    for(int i=1;i<=N;i++) getline(cin,code[i]);
    return;
}

char subcode[10005]; //命令名称
char pm[5][10005]; //参数
int pmcnt; //参数个数

void run(){
//    printf("\"%s\" %d\n",subcode,pmcnt);
    /*if(nowline == 8){
        printf("\"%s\" %d:",subcode,pmcnt);
        for(int i=1;i<=pmcnt;i++){
            printf("\"%s\" ",pm[i]);
        }
        puts("");
    }*/
    
    if(subcode==(string)"udef") control::udef();
    if(subcode==(string)"hlt") control ::hlt();
    if(subcode==(string)"nop") control ::nop();
    if(subcode==(string)"set") control::set(pm[1],pm[2]);
    if(subcode==(string)"jmp") control::jmp(pm[1]);
    if(subcode==(string)"jif"){
        if(pmcnt == 1) control::jif(pm[1]);
        if(pmcnt == 2) control::jif(pm[1],pm[2]);
    }
    if(subcode==(string)"call") control::call(pm[1]);
    if(subcode==(string)"ret"){
        if(pmcnt == 0) control::ret();
        if(pmcnt == 1) control::ret(pm[1]);
    }
    
    
    
    if(subcode==(string)"inv"){
        if(pmcnt == 1) arithmetic::inv(pm[1]);
        if(pmcnt == 2) arithmetic::inv(pm[1],pm[2]);
    }
    if(subcode==(string)"add"){
        if(pmcnt == 2) arithmetic::add(pm[1],pm[2]);
        if(pmcnt == 3) arithmetic::add(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"sub"){
        if(pmcnt == 2) arithmetic::sub(pm[1],pm[2]);
        if(pmcnt == 3) arithmetic::sub(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"mult"){
        if(pmcnt == 2) arithmetic::mult(pm[1],pm[2]);
        if(pmcnt == 3) arithmetic::mult(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"idiv"){
        if(pmcnt == 2) arithmetic::idiv(pm[1],pm[2]);
        if(pmcnt == 3) arithmetic::idiv(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"mod"){
        if(pmcnt == 2) arithmetic::mod(pm[1],pm[2]);
        if(pmcnt == 3) arithmetic::mod(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"lsft"){
        if(pmcnt == 2) arithmetic::lsft(pm[1],pm[2]);
        if(pmcnt == 3) arithmetic::lsft(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"rsft"){
        if(pmcnt == 2) arithmetic::rsft(pm[1],pm[2]);      
        if(pmcnt == 3) arithmetic::rsft(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"band"){
        if(pmcnt == 2) arithmetic::band(pm[1],pm[2]);
        if(pmcnt == 3) arithmetic::band(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"bor"){
        if(pmcnt == 2) arithmetic::bor(pm[1],pm[2]);
        if(pmcnt == 3) arithmetic::bor(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"bxor"){
        if(pmcnt == 2) arithmetic::bxor(pm[1],pm[2]);
        if(pmcnt == 3) arithmetic::bxor(pm[1],pm[2],pm[3]);
    }
    
    
    if(subcode==(string)"lgr"){
        if(pmcnt == 2) logic::lgr(pm[1],pm[2]);
        if(pmcnt == 3) logic::lgr(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"lls"){
        if(pmcnt == 2) logic::lls(pm[1],pm[2]);
        if(pmcnt == 3) logic::lls(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"lge"){
        if(pmcnt == 2) logic::lge(pm[1],pm[2]);
        if(pmcnt == 3) logic::lge(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"lle"){
        if(pmcnt == 2) logic::lle(pm[1],pm[2]);
        if(pmcnt == 3) logic::lle(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"leql"){
        if(pmcnt == 2) logic::leql(pm[1],pm[2]);
        if(pmcnt == 3) logic::leql(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"land"){
        if(pmcnt == 2) logic::land(pm[1],pm[2]);
        if(pmcnt == 3) logic::land(pm[1],pm[2],pm[3]);
    }
    if(subcode==(string)"lor"){
        if(pmcnt == 2) logic::lor(pm[1],pm[2]);
        if(pmcnt == 3) logic::lor(pm[1],pm[2],pm[3]);
    }
    
    if(subcode==(string)"rint"){
        if(pmcnt == 0) input::rint();
        if(pmcnt == 1) input::rint(pm[1]);
    }
    if(subcode==(string)"rch"){
        if(pmcnt == 0) input::rch();
        if(pmcnt == 1) input::rch(pm[1]);
    }
    if(subcode==(string)"wint"){
        if(pmcnt == 0) output::wint();
        if(pmcnt == 1) output::wint(pm[1]);
    }
    if(subcode==(string)"wch"){
        if(pmcnt == 0) output::wch();
        if(pmcnt == 1) output::wch(pm[1]);
    }
    return;
}

signed main(){
    N=read();
    getcode();
    init();
    
    for(nowline=1;nowline<=N;nowline++){
        int pos=0;
        while(pos<code[nowline].size() && code[nowline][pos] == ' ') pos++; //跳过开头所有的逗号和空格
        if(pos == code[nowline].size()) continue; //如果是空行就跳过
        sscanf(code[nowline].substr(pos).c_str(),"%[^ ,;]",subcode); //读取命令名称，直到分号、逗号、空格、三者之一
        pos+=strlen(subcode);
        
        
        while(code[nowline][pos] == ' ' || code[nowline][pos] == ',') pos++; //跳过所有的逗号和空格
        
        pmcnt=0;
        while(code[nowline][pos] != ';'){ //读取参数
            pmcnt++;
            sscanf(code[nowline].substr(pos).c_str(),"%[^ ,;]",pm[pmcnt]); //读取到分号、逗号、空格、三者之一为止
            pos+=strlen(pm[pmcnt]);
            
            while(code[nowline][pos] == ' ' || code[nowline][pos] == ',') pos++; //跳过所有的逗号和空格
        }
        run();
    }
    /*
    for(int i=1;i<=N;i++){
        cout<<code[i]<<endl;
    }
    */
    return 0;
}

做完了以上工作，本题便可以成功AC了。