P3695 CYaRon!语题解

Untitled10032 · 2022-11-24 09:34:11 · 题解

NOIP 临近，据之前模拟赛的经验来看，正解我大概的确是想不出来了，但是暴力还老是写挂。所以想做一道大模拟练练手。结果脑子一抽做了这道题，差点死在 VS code 里。

我采用的是类似编译器的方法。先把所有语句都解析之后存起来之后再运行。

语句的存储

（先给每种命令设置一个“ID”）：

enum Opt {
    YOSORO, SET, IHU, JMP, HOR, WHILE, VARS, DEC
    //JMP: 跳到指定指令，最终处理结果中不含有 while。
    //DEC：自减运算。
};

enum Operator {
    LT, GT, LE, GE, EQ, NEQ, ERR    //ERR: 错误的符号
};

整个程序中的语句用 vector 存起来，语句中的参数可能是在解析输入的时候不能确定的值，所以用链表存储一个表达式，里面是需要引用的变量的地址、偏移量（数组下标有时也不能在解析的时候确定）。

struct Arg {
    int *addr;
    Arg *addrShift; //偏移量（因为需要考虑变量做下标）
    bool positive;  //true:+, false:-
    Arg *nxt;   //需要保证链表尾项nxt为NULL
};
class Statement {
public:
    Opt opt;
    Arg *args[mxStatArg];
    Statement(Opt option) {
        opt = option;
    }
};
vector<Statement> program;

常量的存储

存储语句时肯定会遇到一些常量。我采取的方法是开一个专门存储常量的数组，遇到常量就放进数组里，然后拿出指针。

int constPool[constPoolSize], cntConst = 0;

什么？你说可以直接在存储语句的类里面开几个 int 的空间或者存的时候直接用 new 分配一个地址？我后来才想到这些的，懒得改了。反正就这样也不错。

变量的存储

分数和数组两个 map 存储。

map<string, int> integers;
struct Array {
    int delta;
    int arr[mxArraySize];
    Array(int bg, int en) {
        memset(arr, 0, (en - bg + 3) * sizeof(int));
        delta = bg;
    }
    int& operator [] (int pos) {
        return arr[pos - delta];
    }
};
map<string, Array> arrays;

数组需注意下标问题。这里我直接将对整个 struct 的下标运算符重载成了访问偏移后的下标。

解析输入

将解析输入部分封装成了一个类（Processer）：

class Processer {
    char inputBuf[inBufSize];
    char *cursor;

    inline string getNextWord();    //提取下一个词（需保证词在本行内）
    inline bool endOfLine();        //光标后换行前没有有意义的东西
    inline bool eof();              //光标已经跑到了没有数据的荒原
    inline void nextCommandLine();  //跳到下一个有意义的行
    inline void skipSpace();        //跳过空格
    inline void skipChar(char);     //跳过任意多个空格和任意多个指定字符的任意排列
    inline int readNum();           //读取下一个数
    inline int readNum(string);     //从string读取数
    inline Operator judgeOper(string);  //判断不等式（判断式）的符号
    inline Arg* judgeVar(string);       //返回变量的地址
    inline Arg* analyzeFormula();       //解析算式（返回解析后的链表首指针）
    inline void error(const char *);    //报告错误
public:
    Processer();
    inline void getInput(); //将输入全部读入
    inline void proc();     //处理
}processer;

（函数的定义请看文末源代码）

为了运行时好处理，新定义了两个指令：

jmp：跳到指定指令。
dec：自减运算。

给每种类型规定了参数的存储顺序：

ihu: 不等式符号，不等式左，不等式右，若表达式不成立则跳到哪行
hor: 循环变量，循环变量的最大值，若表达式不成立则跳到哪行
set: 被赋值的变量, 赋过去的值
jmp: 指令序号
dec: 对象

划分“词”：

将输入分解成许多便于处理的“词”。（这玩意好像流行叫 Token，但我就叫它 word，懒得改了）

getNextWord 函数如果遇到一个括号或其它有用的符号就直接返回这个符号，其它情况则返回下一个由数组和字母组成的字符串。这样可以方便地判断下标、算式符号等。

inline string Processer::getNextWord() {
    while (*cursor == ' ')  cursor++;
    string ret = "";
    if (*cursor == '{' || *cursor == '}' || *cursor == '+' || *cursor == '-' ||
        *cursor == '[' || *cursor == ']' || *cursor == ':' || *cursor == ',')
        ret.push_back(*(cursor++));
    else
        while ((*cursor >= 'a' && *cursor <= 'z') || (*cursor >= 'A' && *cursor <= 'Z') ||
            (*cursor >= '0' && *cursor <= '9'))
            ret.push_back(*(cursor++));
    return ret;
}

将 `hor` 和 `while` 拆分。

hor

将 hor 拆分成 set 与 hor，拆分后的 hor 中只是将循环变量自增，只有判断循环是否应该停止。并在循环结束时 jmp 回循环开始。

hor 伪代码（存储时语句的参数与参数表对应）：

原格式：
{   hor var, bg, en
    ...
}

存储格式：
:set var, bg - 1
hor bg, en, jmp的下一行
...
jmp hor那一行

while

将 while 转换成 ihu，并在循环结束时 jmp 回循环开始。

while 伪代码：

原格式：
{   while oper, left, right
    ...
}

存储格式：
ihu oper, left, right, jmp的下一行
...
jmp ihu那一行

大括号问题

使用了一个栈来存储大括号。

struct Brace {
    Opt opt;    //前大括号是什么指令
    int bg;     //前大括号在第几个指令
};
stack<Brace> braces;

遇到前括号压栈（vars 除外，处理 vars 时会顺便把后括号吃掉），遇到后括号取栈顶、弹栈并填入响应语句与参数。

注意：输入数据最后可能没有换行。

运行

将运行部分封装成了一个类（Runner）：

class Runner {
    int calc(Arg *);
    inline bool judge(int, int, int);
    inline void error(const char *, int);
public:
    inline void run();
}runner;

（函数的定义请看文末源代码）

~~封装了个寂寞~~

运行就比较简单了。

写了一个递归函数（calc）去计算每个表达式的值。

int Runner::calc(Arg *a) {
    if (a == NULL)
        return 0;
    const int res = *(a->addr + calc(a->addrShift));
    if (a->positive)
        return calc(a->nxt) + res;
    else
        return calc(a->nxt) - res;
}

之后将语句一个一个往下执行，把对应的参数拿出来参与运算，如果需要跳转就跳到对应的行，否则执行下一个语句。如果执行完了就停。就行了。

源代码

附录单词表

单词	释义
statement	这里指单个语句（这个用法好像不常见）。
brace	大括号。
word	就是大佬们说的 token，即将字符串划分成的便于处理的子串。
formula	这里指算式、表达式。（这个词好像一般指公式，建议不要像我这样用）

以下是较常见/简单的单词：

单词	释义
cursor	指光标。
opt	为 option 的简写。选项，选择。
calc	为 calculate 或 calculation 的简写。计算。
analyze	分析，解析。
arg	为 argument 的简写。指实际参数。~~精氨酸~~
positive	这里指一个数为正数。

P3695 CYaRon!语 题解