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

题面

P4911 河童重工的计算机

另外一组样例

样例来自题面中的汇编教程附带示例, 删去了空行, 懒得编数据了, 所以就没有写读入数据部分.

点我查看样例

26
[ progfunc.asm ]
[ Shows the function functionailties of the KTX-65 ALI ]
[main]
wint #line;    [output the current physical line number]
wch 13;        [putchar \r]
wch 10;        [putchar \n]
callfunc $Function1;
callfunc $Function2;
hlt;           [halt]
function $Function1;
rint %r1;      [read int]
add %r2 1 %r2; [loop contents]
lle %r2 %r1;   [loop conditions]
jif 2;         [end loop conditional jump]
wint %r2;      [output int]
wch 13;        [putchar \r]
wch 10;        [putchar \n]
ret;           [return]
function $Function2;
rint %r1;      [read int]
rint %r2;      [read int]
add %r1, %r2;  [add]
wint %val;     [output value]
wch 13;        [putchar \r]
wch 10;        [putchar \n]
ret;           [return]

样例看不懂也没关系, 下面是用C++的语句转换的程序, 为了方便对应行号, 转换后的样例删去了第一个空行, 同时每条语句前加上了操作码.

点我查看转换后的样例

28 cout << line;
29 cout << '\r';
29 cout << '\n';
31 fun1();
31 fun2();
1 exit();
30 fun1(){
26    cin >> r1;
9    r2++;
22    flag = r2 <= r1;
5    if (flag) goto Line 11;
28    cout << r2;
29    cout << '\r';
29    cout << '\n';
7    return;}
30 fun2(){
26    cin >> r1;
26    cin >> r2;
9    val = r1 + r2;
28    cout << val;
29    cout << '\r';
29    cout << '\n';
7    return;}

架构设计

写大模拟应该做什么? 当然是跑路啊, 不跑路还留下来秃头吗? 当然是先分析需求, 设计基本架构啊.

首先观察指令格式, 可以发现一个操作至多只有三个变量(开个数组就完事了).

再来观察变量, 一些类型的变量需要读写寄存器或者内存, 存个指针就可以了, 另一些变量是常量, 标记一下即可.

接下来观察内存和栈, 根据文档可知, 直接开个数组模拟即可.

如何将指令与操作联系起来呢? 我们只要给每种指令编号, 用编号去访问不同的函数就可以了, 开个map<string, int> 就可以了.

读入预处理

首先我们先预处理一下所有指令, 统一转换成小写字母.

transform(line.begin(), line.end(), line.begin(), ::tolower);

接下来我们处理注释, 并且给语句分行(应对一行多条语句的情况, 虽然测试数据中貌似并没有这种情况), 顺便还能处理一下变量间可能出现的逗号.

对于注释很简单, 根据未配对的中括号个数就能很容易的判断在不在注释里, 用erase()删除即可, 需要注意的是删除之后迭代器要减一, 否则无法遍历所有字符.

分号代表语句的结束, 利用stringstream的特性, 这里我们把它换成''.

逗号很简单, 换成空格即可.

读入指令

预处理完之后, 我们就获得一个便于处理的string了, 首先存入stringstream, 然后每次读取一行, 就获得了一条指令, 需要注意的是这里可能获得空行, 应该加以判断.

对于每条指令, 操作是必然存在的, 直接无脑读即可, 但是变量个数可能是不确定的, 这里继续利用stringstream的特性来处理.

对于一个变量, 如果它不是常量, 我们直接储存对应指针, 如果是常量, 存储它的值. 具体的处理逻辑在data结构体中的init()函数中.

因为代码太长了, 所以请看完整代码中的对应部分.

函数指针数组

把操作码当作下标访问对应的函数即可.

void (*fun[])(const op &a, int &index) = {
    fun0, fun1, fun2, fun3, fun4, fun5, fun6, fun7, fun8, fun9, 
    fun10, fun11, fun12, fun13, fun14, fun15, fun16, fun17, fun18, fun19, 
    fun20, fun21, fun22, fun23, fun24, fun25, fun26, fun27, fun28, fun29, 
    fun30, fun31
};
//example
fun[ops[i].op](ops[i], i);

对应函数

按照题意模拟即可

完整代码

点我查看完整代码

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

#ifdef LOCAL
#define debug(format, args...) \
printf(format, ##args)
#else
#define debug(format, args...)
#endif

using namespace std;

typedef map<string, int> msi;
typedef map<int, int> mii;
typedef stringstream SS;

msi op2fun = {{"udef", 0}, {"hlt", 1}, {"nop", 2}, {"set", 3}, {"jmp", 4},
{"jif", 5}, {"call", 6}, {"ret", 7}, {"inv", 8}, {"add", 9}, {"sub", 10},
{"mult", 11}, {"idiv", 12}, {"mod", 13}, {"lsft", 14}, {"rsft", 15},
{"band", 16}, {"bor", 17}, {"bxor", 18}, {"lgr", 19}, {"lls", 20},
{"lge", 21}, {"lle", 22}, {"leql", 23}, {"land", 24}, {"lor", 25},
{"rint", 26}, {"rch", 27}, {"wint", 28}, {"wch", 29}, {"function", 30}, {"callfunc", 31}};

msi reg2pointer = {{"r1", 0}, {"r2", 1}, {"r3", 2}, {"r4", 3}, {"e1", 4},
{"e2", 5}, {"e3", 6}, {"e4", 7}, {"flag", 8}, {"val", 9}, {"ret", 10}, {"line", 11}};

//funLine for the line of the first statement of function
//funIndex for the index in vecor of the first statement of function
//funNum for the Num of the function 
//line2index for transform line to index in vector
mii funLine;
mii funIndex;
msi funNum;
mii line2index;

int r1, r2, r3, r4, e1, e2, e3, e4, flag, val, ret, line, falseVar, funCnt = 0, statementCnt = 0;

int *reg[] = {&r1, &r2, &r3, &r4, &e1, &e2, &e3, &e4, &flag, &val, &ret, &line};

int ram[(1 << 23) + 9];
int sAddr[(1 << 19) + 9];

struct data{
    int* a;
    int value;
    //0 for register, 1 for constant, 2 for adress, 3 for adress in register
    //4 for Line, 5 for inputInt, 6 for inputChar, 7 for outputInt, 8 for outputChar 
    //9 for initFunction, 10 for callFunction
    int type;
    void out(){
        debug("\t%d %d\n", value, type);
    }
    data (int *A = &falseVar, int v = 0, int t = -1): a(A), value(v), type(t){	
    }
    void init(string &s, int L){
        auto it = s.begin();
        if (s[0] == '%'){
            type = 0;
            s.erase(it);
            a = reg[reg2pointer[s]];
        }
        else if (s[0] == '@'){
            if (s[1] == '%'){
                type = 3;
                s.erase(it);
                s.erase(it);
                a = reg[reg2pointer[s]];
            }
            else{
                type = 2;
                s.erase(it);
                value = stoi(s);
                a = &ram[value];
            }
        }
        else if (s[0] == '#'){
            a = &falseVar;
            value = L;
            type = 4;
        }
        else{
            type = 1;
            a = &falseVar;
            value = stoi(s);
        }
    }
};

struct op{
    int op;
    data d[3];
    //line for the number of current statement
    //funLine for the number in function of current statement
    int line, funLine;
};

int getValue(const op &a, int index){
    int b = 0;
    switch (a.d[index].type){
        case 0:{
        }
        case 2:{
            b = *(a.d[index].a);
            break;
        }
        case 3:{
            b = ram[*(a.d[index].a)];
            break;
        }
        case 1:{
            b = a.d[index].value;
            break;
        }
        case 4:{
            b = a.line;
            break;
        }
    }
    return b;
}

void fun0(const op &a, int &index){
}
void fun1(const op &a, int &index){
}
void fun2(const op &a, int &index){
}
void fun3(const op &a, int &index){
    int b = getValue(a, 0);
    *(a.d[1].a) = b;
    debug("\nFun3: b: %d line: %X %X;\n", b, *(a.d[1].a), &line);
}
void fun4(const op &a, int &index){
    int b = getValue(a, 0);
    index = line2index[line + b];
}
void fun5(const op &a, int &index){
    int Flag = getValue(a, 1);
    int b = getValue(a, 0);
    if (Flag){
        index = line2index[line + b] - 1; 
    }
}
void fun6(const op &a, int &index){
    int &top = sAddr[0];
    top++;
    sAddr[top] = index;
    debug("PushIndex: %d\n", index + 1);
    top++;
    sAddr[top] = line;
    int b = getValue(a, 0);
    index = line2index[b] - 1;
}
void fun7(const op &a, int &index){
    int &top = sAddr[0];
    int Line = sAddr[top];
    line = Line;
    top--;
    int next = sAddr[top];
    top--;
    index = next;
    debug("NextIndex: %d\n", next);
    if (a.d[0].value != -1){
        int b = getValue(a, 0);
        ret = b;
    }
}
void fun8(const op &a, int &index){
    int b = getValue(a, 0);
    b = -b;
    *(a.d[1].a) = b;
}
void fun9(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = b + c;
    debug("\nFun9: b: %d c: %d ans: %d;\n", b, c, *(a.d[1].a));
}
void fun10(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = b - c;
}
void fun11(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = b * c;
}
void fun12(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = b / c;
}
void fun13(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = b % c;
}
void fun14(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = b << c;
}
void fun15(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = b >> c;
}
void fun16(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = b & c;
}
void fun17(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = b | c;
}
void fun18(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = b ^ c;
}
void fun19(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = (b > c);
}
void fun20(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = (b < c);
}
void fun21(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = (b >= c);
}
void fun22(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = (b <= c);
}
void fun23(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = (b == c);
}
void fun24(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = b && c;
}
void fun25(const op &a, int &index){
    int b = getValue(a, 0);
    int c = getValue(a, 1);
    *(a.d[2].a) = b || c;
}
void fun26(const op &a, int &index){
    cin >> *(a.d[0].a);
}
void fun27(const op &a, int &index){
    cin >> *(a.d[0].a);
}
void fun28(const op &a, int &index){
    cout << getValue(a, 0);
}
void fun29(const op &a, int &index){
    cout << (char)getValue(a, 0);
}
void fun30(const op &a, int &index){
    line = a.line;
    debug("Line: %d\n", line);
}
void fun31(const op &a, int &index){
    int b = funIndex[a.d[0].value];
    debug("b: %d\n", b);
    int &top = sAddr[0];
    top++;
    sAddr[top] = index;
    debug("PushIndex: %d\n", index + 1);
    top++;
    sAddr[top] = line;
    index = b - 1;
}

void (*fun[])(const op &a, int &index) = {
    fun0, fun1, fun2, fun3, fun4, fun5, fun6, fun7, fun8, fun9, 
    fun10, fun11, fun12, fun13, fun14, fun15, fun16, fun17, fun18, fun19, 
    fun20, fun21, fun22, fun23, fun24, fun25, fun26, fun27, fun28, fun29, 
    fun30, fun31
};

typedef vector<op> vo;

int main(){
    #ifndef LOCAL
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif 
    int n;
    cin >> n;
    cin.get();
    vo ops;
    int funFlag = 0;
    for (int i = 0; i < n; i++){
        string line;
        getline(cin, line, '\n');
        transform(line.begin(), line.end(), line.begin(), ::tolower);
        auto it = line.begin();
        int zkh = 0;
        for (; it < line.end(); it++){
            if (zkh){
                if (*it == ']'){
                    zkh--;
                }
                line.erase(it);
                it--;
            }
            else{
                if (*it == ','){
                    *it = ' ';
                }
                else if (*it == ';'){
                    *it = '\n';
                }
                else if (*it == '['){
                    zkh++;
                    line.erase(it);
                    it--;
                }
                //position is wrong
                /*else if (*it == ']'){
                    zkh--;
                    line.erase(it);
                    it--;
                }*/
            }
        }
        SS ss(line);
        string s;
        while (getline(ss, s, '\n')){
            SS ssTemp(s);
            string command;
            ssTemp >> command;
            if (command.empty()){
                continue;
            }
            string sTemp;
            int cmd = op2fun[command];
            if (!line2index.count(i)){
                line2index[i] = statementCnt;
            }
            switch (cmd){
                case 0:{
                }
                case 1:{
                }
                case 2:{
                    op T;
                    T.op = cmd;
                    T.line = i;
                    ops.push_back(T);
                    break;
                }
                case 5:{
                    string a, b;
                    int cnt = 0;
                    op T;
                    T.op = cmd;
                    T.line = i;
                    ssTemp >> a;
                    T.d[0].init(a, i);
                    if (!(ssTemp >> b) || b.empty()){
                        string fake = "%flag";
                        T.d[1].init(fake, i);
                    }
                    ops.push_back(T);
                    break;
                }		
                case 7:{
                    op T;
                    T.op = cmd;
                    T.line = i;
                    string a;
                    if (ssTemp >> a && !a.empty()){	
                    }
                    else{
                        a = "%ret";
                    }
                    T.d[0].init(a, i);
                    ops.push_back(T);
                    break;
                }
                case 4:{
                }
                case 6:{
                    op T;
                    T.op = cmd;
                    T.line = i;
                    string a;
                    ssTemp >> a;
                    T.d[0].init(a, i);
                    ops.push_back(T);
                    break;
                }
                case 8:{
                    string a, b;
                    ssTemp >> a;
                    if (ssTemp >> b && !b.empty()){
                    }
                    else{
                        b = "%val";
                    }
                    op T;
                    T.op = cmd;
                    T.line = i;
                    T.d[0].init(a, i);
                    T.d[1].init(b, i);
                    ops.push_back(T);
                    break;
                }
                case 3:{
                    string a, b;
                    ssTemp >> a >> b;
                    op T;
                    T.op = cmd;
                    T.line = i;
                    T.d[0].init(a, i);
                    T.d[1].init(b, i);
                    ops.push_back(T);
                    break;
                }
                case 9:{
                }
                case 10:{
                }
                case 11:{
                }
                case 12:{
                }
                case 13:{
                }
                case 14:{
                }
                case 15:{
                }
                case 16:{
                }
                case 17:{
                }
                case 18:{
                    string a, b, c;
                    ssTemp >> a >> b;
                    if (ssTemp >> c && !c.empty()){
                    }
                    else{
                        c = "%val";
                    }
                    op T;
                    T.op = cmd;
                    T.line = i;
                    T.d[0].init(a, i);
                    T.d[1].init(b, i);
                    T.d[2].init(c, i);
                    ops.push_back(T);
                    break;
                }
                case 19:{
                }
                case 20:{
                }
                case 21:{
                }
                case 22:{
                }
                case 23:{
                }
                case 24:{
                }
                case 25:{
                    string a, b, c;
                    ssTemp >> a >> b;
                    if (ssTemp >> c){
                    }
                    else{
                        c = "%flag";
                    }
                    op T;
                    T.op = cmd;
                    T.line = i;
                    T.d[0].init(a, i);
                    T.d[1].init(b, i);
                    T.d[2].init(c, i);
                    ops.push_back(T);
                    break;
                }
                case 26:{
                    string a;
                    if (ssTemp >> a && !a.empty()){
                    }
                    else{
                        a = "%val";
                    }
                    op T;
                    T.op = cmd;
                    T.line = i;
                    T.d[0].init(a, i);
                    T.d[0].type = 5;
                    ops.push_back(T);
                    break;
                }
                case 27:{
                    string a;
                    if (ssTemp >> a && !a.empty()){
                    }
                    else{
                        a = "%val";
                    }
                    op T;
                    T.op = cmd;
                    T.line = i;
                    T.d[0].init(a, i);
                    T.d[0].type = 6;
                    ops.push_back(T);
                    break;
                }
                case 28:{
                    string a;
                    if (ssTemp >> a && !a.empty()){
                    }
                    else{
                        a = "%val";
                    }
                    op T;
                    T.op = cmd;
                    T.line = i;
                    T.d[0].init(a, i);
                    //T.d[0].type = 7;
                    ops.push_back(T);
                    break;
                }
                case 29:{
                    string a;
                    if (ssTemp >> a && !a.empty()){
                    }
                    else{
                        a = "%val";
                    }
                    op T;
                    T.op = cmd;
                    T.line = i;
                    T.d[0].init(a, i);
                    //T.d[0].type = 8;
                    ops.push_back(T);
                    break;
                }
                case 30:{
                    string a;
                    ssTemp >> a;
                    op T;
                    T.op = cmd;
                    T.line = i;
                    int num = 0;
                    if (!funNum.count(a)){
                        num = funNum[a] = funCnt++;
                    }
                    else{
                        num = funNum[a];
                    }
                    funIndex[num] = ops.size();
                    funFlag = 1;
                    T.d[0].value = i;
                    T.d[0].type = 10;
                    ops.push_back(T);
                    break;
                }
                case 31:{
                    string a;
                    ssTemp >> a;
                    op T;
                    T.op = cmd;
                    T.line = i;
                    int num = 0;
                    if (!funNum.count(a)){
                        funNum[a] = funCnt++;
                    }
                    num = funNum[a];
                    T.d[0].value = num;
                    T.d[0].type = 1;
                    ops.push_back(T);
                    break;
                }
            }
            statementCnt++;
        }
    }
    /*int cnt = 0;
    for (auto x : ops){
        cout << cnt << ": " << x.op << '\n';
        for (int i = 0; i < 3; i++){
            x.d[i].out();
        }
        cnt++;
    }*/
    line = ops[0].line;
    for (int i = 0; i < statementCnt; i++){
        if (ops[i].op == 1){
            return 0;
        }
        else{
            fun[ops[i].op](ops[i], i);
            debug("\n| op: %d; r1: %d; r2: %d; val: %d; line: %d; %%line: %d; index: %d; |\n", 
                ops[i].op, r1, r2, val, ops[i].line, line, i);
            //fun[ops[i].op](ops[i], i);
        }
    }
    return 0;
}