题解 P3695 【CYaRon!语】

Ciyang · 2020-01-11 18:21:43 · 题解

BLOG中查看体验更佳。

前言

给出解释器的相关内容，国外文献及国内翻译，文献所用语言是Python，并且国内只有计算器的部分（加减乘除，相反数）。

所以我写代码的时候更加注重工程风格，在保证无BUG前提下尽量严格，并且不依赖于其他库（STL）。

如果在代码中调用了我没有讲的函数，那么请看最后的完整代码，因为函数实在太多了。类中必要的public函数基本都已省略。代码中...表示省略

解释器概述

建议先编写一个表达式求值，不过这道题需要处理的中缀表达式中只有加减运算，所以比较简单。

写一下的解释器通用的逻辑。

TOKEN

翻译为令牌、标记，我理解为单词，包括单关键字、变量名、符号等。

主要是将一段字符串转换为计算机可以理解的东西，通常是数字。每个TOKEN都有它自己的类型，并且存储原有的内容。TOKEN通常是解释器的最小单元。

具体实现可以用define、const、enum之一，我使用了enum。这些都是程序员自己定义的。例如此题（部分）：

enum TOKEN_TYPE {
    INTEGER = 1,    // 整形（数字）
    OPERATOR_PLUS,  // 操作符 '+'
    ...,
    T_COLON,        // 符号 ':'
    T_COMMA         // 符号 ','
};
// TOKEN 类型

存储时即使用类或者结构体，代码（部分）：

class TOKEN {
    private:
    TOKEN_TYPE _typ;    // TOKEN类型
    const char *_val;   // 原有的值
    unsigned int _len;  // 值长度
    // 注：使用 const char* 是为了方便
    ...
};

LEXER

翻译为词法分析器。简单来说，输入一堆字符（本题是整个程序），经过LEXER的处理，输出一系列的TOKEN（按顺序）。

对于大部分OIER来说，都写过暴力模拟的表达式求值。两者想似，但是LEXER分析一段字符串后输出TOKEN并不直接让LEXER来处理。所以它还有个别名为scanner。

存储时依然是使用类或者结构体，代码（部分）：

class LEXER {
    private:
    const char *_text;  // 一堆字符（本题是整个程序）
    unsigned int _len;  // 字符长度
    unsigned int _pos;  // 处理到第_pos个字符（从 0 开始）
    char _ch;           // 当前字符为_ch
    ...
}

然后要在类中写几个函数，分别是扫描下一个字符、跳过间隔符、跳过数字等。扫描下一个字符时要判断是否已到字符串结尾，代码：

void nextChar() {
    this->_ch = (this->_pos >= this->_len ? 0 : this->_text[++this->_pos]);
    return;
}
unsigned int skipNumber() {
    unsigned int res = 0;
    while(this->_ch != 0 && isNumber(this->_ch)) ++res, nextChar();
    // isNumber(x) 表示 x 是否为数字
    return res;
}

LEXER最重要的作用还是获取TOKEN，对于本题的代码（部分）：

TOKEN getNextToken() {
    while(this->_ch != 0) {
        if(isSpacer(this->_ch)) {
        // isSpacer(x) 表示 x 是否为间隔符
            skipSpace();
        // skipSpace() 跳过间隔符
            continue;
        }
        if(isNumber(this->_ch)) {
        // isNumber(x) 表示 x 是否为数字
            const char *pos = getPosString();
            return TOKEN(INTEGER, pos, skipNumber());
        }
        if(this->_ch == '+') {
            nextChar();
            return TOKEN(OPERATOR_PLUS);
        }
        ...
        if(this->_ch == ',') {
            nextChar();
            return TOKEN(T_COMMA);
        }
        if(this->_ch == ':') {
            nextChar();
            return TOKEN(T_COLON);
        }
        return TOKEN(T_NULL);
        // 无法处理
    }
    return TOKEN(T_EOF);
    // 结尾
}

NODE

NODE是我起的名字，因为它代表语法树的一个节点。获得程序根节点的返回值意味着运行整个程序。

每个NODE存储一个TOKEN，TOKEN的类型表示NODE的任务类型，TOKEN的值表示NODE可用的参数。NODE还有它的子节点，每个NODE运作时都会用指定方式使它的子节点运作。

它的类在此题如下：

class NODE {
    private:
    TOKEN _token;               // 必需的
    NODE **_list;               // 子节点指针数组
    bool _multi;
    unsigned int _siz, _msiz;
    bool _flag;
}

_multi、_msiz、_flag是我的实现，可能有更好的方法。至于它们的作用会在下面再讲。

NODE的两个核心方法为getValue和setValue，但对于本题来说，前置更复杂一些。

PARSER

翻译为语法分析器。输入TOKEN，生成语法树，输出根节点。因为此题不涉及运算符先后顺序，所以只需实现判断。循环等语法即可。

PARSER类的代码（部分）：

class PARSER {
    private:
    LEXER _lexer;   // 绑定的LEXER
    TOKEN _tok;     // 当前处理的TOKEN
    ...
};

同样在类中有获得下一个TOKEN的函数，代码：

void nextToken(TOKEN_TYPE typ) {
    if(this->_tok.getType() == typ) this->_tok = this->_lexer.getNextToken();
    return;
}

有方法parser用来生成语法树，内部由多个函数递归实现，因语言而异。

CALCULATOR

推荐先写一个加减乘除相反数的计算器来练手，此处为我的代码。

本题分析

计算器和本题差别还是很大的，对比发现，本题多了变量、判断、循环、数组、输出、比较，少了乘除。再进一步发现，少了运算优先级的问题。

TOKEN

我定义本题有30个TOKEN，可以说是非常多了，所以请对照完整代码。然后只讲一些本题的核心语法和逻辑。

如果不知道某个TOKEN_TYPE的含义，那么请看在代码里的LEXER中TOKEN是如何产生的。

VARIABLE

至于为什么先讲这个，因为程序一上来就要定义变量。我是针对本题只有int来解决的，解释器文献的这部分在C++中出入较大。

本着不用STL的原则，因此无法使用map。我并不想也不会写红黑树，而本题只有10个变量，所以就链表查询变量了。代码（部分）：

class VAR {
    private:
    const char *_name;  // 变量名
    unsigned int _len;  // 变量名长度
    VAR *_nxt;          // 链表下一个
    int *_mem;          // 内存
    int _s, _t;         // 数组下标起始和终止，非数组中分别为0、1
    ...
};

然后定义一个链表首节点var_first，写两个函数分别为getVar、setVar，前置是根据名称获得VAR指针，后者实际上是注册一个VAR。

BLOCK

BLOCK是一个TOKEN类型，目的表示代码块。一个{}所包含的内容即是一个代码块，特别的，整个程序也是一个代码块。

根据语言的特性，代码块的第一行通常为控制语句，比如判断、循环、vars等。如果没有控制语句，设置BLOCK为默认控制语句，代表只运行一次，vars也是如此。

我们将根据第0个子节点的返回值是否为true循环运行BLOCK中的内容。

NODE

所以问题又来了，如何存储子节点列表。我们并不想使用vector，只好自己实现。

根据vector的思想，只需要在列表已满时将空间扩大一倍（变为两倍），效率比较高。

为了方便使用，特化出自运算、一元运算和二元运算，以提高代码复杂度便于编写。

按照规则，BLOCK表示代码块时是多元运算。如果BLOCK表示控制语句时是自运算。

因此在代码中用_multi表示是否为多元运算，_siz记录子节点数，_msiz记录分配内存大小。

VARIABLE_DEFINE

首先知道格式为name:type/array[type, s..t]，即名称:类型/数组[类型, 起始下标..终止下标]。

那么组成它的TOKEN包括VARIABLE_NAME、VARIABLE_TYPE、BRACKET_LEFT、BRACKET_RIGHT、INTEGER、T_DOT。

语法树构建时，我把T_COLON设为多元运算符，VARIABLE_NAME设为第0子节点，省去了VARIABLE_TYPE，如果为数组再新建两个INTEGER节点当做T_COLON的子节点。

此为parserVar函数。

运作时判断子节点数，VAR中的_s为第1个子节点的值，_t为第2个子节点的值，无子节点视为0、1。

EXPRESSION

表达式已经是老生常谈的问题了，所以不再细说。

遇到表达式调用parserSecond，内部调用parserThird，分析出常量、变量、加减运算符，遇到括号（然而此题没有，才发现）就递归调用parserSecond。

VARIABLE

读取变量的值时先读入VARIABLE_NAME，再判断是否有BRACKET_LEFT（左中括号），之后再调用parserSecond读取内部表达式，再读入BRACKET_RIGHT，然而本题内部表达式并不会很复杂。

所以此处我把VARIABLE_NAME设为一元运算符，仅有的一个子节点为下标（不是数组则为0）。

YOSORO | ASSIGN(SET)

先分析输出和赋值语句，因为它们逻辑最简单且作用相反（似乎并不相反）。

当PARSER遇到类型为T_COLON的TOKEN时，那么就视为要执行函数了，进入parserCall函数。

YOSORO为一元运算符，仅有一个子节点为表达式。ASSIGN为二元运算符，左儿子为变量名，右儿子为表达式。

IF(IHU) | WHILE

之所以它们放在一块，是因为语法相同。当遇到对应的TOKEN时，依次读取比较操作符、逗号、表达式、逗号、表达式，函数为parserIhu和parserWhile。

IF和WHILE为一元运算符，仅有一个子节点为比较操作符的返回值。众所周知比较操作符是二元运算符，这个非常简单。

为了判断一个节点是否第一次运作，所以在NODE中加入了变量_flag。

IF和WHILE的差别在于IF后需要将_flag设为true。

BLOCK 1

在BLOCK运作结束后还需要重置子节点的状态信息（如_flag），以让下次进入BLOCK节点时所有的子节点是新的。

FOR(HOR)

FOR应该是比较麻烦的一个，我将它设为多元运算符。

函数为parserHor，依次读取表达式、逗号、表达式、逗号、表达式。三个表达式依次为它的三个子节点。

运作时先判断_flag，第一次需要给第0个子节点赋值为第1个子节点的值。然后再通过判断第0个子节点是否小于等于第2个子节点。

还需要让FOR节点也要有一个赋值的方法，为了在循环结束时给第0个子节点加1。

BLOCK 2

所以BLOCK结束时还要调用控制语句（第0个子节点）的赋值操作，当然值就不必设置了。

GLOBAL FUNCTION

运行程序使用calc，参数为整个程序和字符串长度。

int calc(const char *exp, unsigned int len) {
    char *_exp = new char[len]();
    for(unsigned int i = 0; i < len; i++) _exp[i] = exp[i];
    // 改为用户不可变内存，安全起见
    int res = PARSER(LEXER(_exp, len)).parser()->getValue();
    delete[] _exp;
    return res;
}

并未使用strcmp，手写了equalString用来判断字符串是否相等。

剩下的方法都比较简单，自行理解即可。

图例

如果还不懂可以看图例，纯手工良心制作。

代码

无O2用时37ms内存820KB

#include <stdio.h>
namespace CALCULATOR {
enum TOKEN_TYPE {
    INTEGER = 1,
    OPERATOR_PLUS,
    OPERATOR_MINUS,
    OPERATOR_LT,
    OPERATOR_GT,
    OPERATOR_LE,
    OPERATOR_GE,
    OPERATOR_EQ,
    OPERATOR_NEQ,
    PAR_LEFT,
    PAR_RIGHT,
    BRACKET_LEFT,
    BRACKET_RIGHT,
    BLOCK_LEFT,
    BLOCK_RIGHT,
    PROGRAM,
    BLOCK,
    VARIABLE_NAME,
    VARIABLE_TYPE,
    VARS,
    YOSORO,
    OPERATOR_ASSIGN,
    IHU,
    HOR,
    WHILE,
    T_DOT,
    T_EOF,
    T_NULL,
    T_COLON,
    T_COMMA
};

bool equalString(const char *a, const char *b, unsigned int len) {
    for(unsigned int i = 0; i < len; i++)
        if(a[i] != b[i]) return 0;
    return 1;
}
class VAR {
    private:
    const char *_name;
    unsigned int _len;
    VAR *_nxt;
    int *_mem;
    int _s, _t;

    public:
    VAR() : _name(), _len(), _nxt(), _mem(), _t(), _s() {}
    VAR(const char *name, unsigned int len) : _name(name), _len(len), _nxt(), _mem(), _t(), _s() {}
    VAR(const char *name, unsigned int len, int s, int t) : _name(name), _len(len), _nxt(), _mem(), _t(t), _s(s) {
        this->_mem = new int[this->_t - this->_s]();
    }
    unsigned int getLen() const {
        return this->_len;
    }
    void setValue(int x, int v) {
        this->_mem[x - this->_s] = v;
        return;
    }
    const char *getName() const {
        return this->_name;
    }
    VAR *getNext() const {
        return this->_nxt;
    }
    void setNext(VAR *v) {
        this->_nxt = v;
    }
    int getValue(int x) {
        return this->_mem[x - this->_s];
    }
} var_first;
VAR *getVar(const char *name, unsigned int len) {
    VAR *p = &var_first;
    while(p) {
        if(p->getLen() == len && equalString(p->getName(), name, len)) return p;
        p = p->getNext();
    }
    return 0;
}
void setVar(VAR *nxt) {
    VAR *p = &var_first;
    while(p->getNext()) p = p->getNext();
    p->setNext(nxt);
    return;
}
class TOKEN {
    private:
    TOKEN_TYPE _typ;
    const char *_val;
    unsigned int _len;

    public:
    TOKEN(TOKEN_TYPE typ = T_NULL) : _typ(typ), _val(), _len() {}
    TOKEN(TOKEN_TYPE type, const char *val, unsigned int len) : _val(val), _typ(type), _len(len) {}
    TOKEN_TYPE getType() const {
        return this->_typ;
    }
    const char *getValue() const {
        return this->_val;
    }
    unsigned int getLength() const {
        return this->_len;
    }
    ~TOKEN() {}
};
int toInteger(const char *val, unsigned int len) {
    int res = 0;
    for(unsigned int i = 0; i < len; i++) res = res * 10 + val[i] - '0';
    return res;
}

unsigned int toString(int val, char *res) {
    unsigned int len = 0;
    int val2 = val;
    while(val2) ++len, val2 /= 10;
    unsigned int len2 = len;
    while(val) res[--len2] = '0' + val % 10, val /= 10;
    if(len == 0) res[len = 1] = '0';
    return len;
}

bool isNumber(char ch) {
    return ch >= '0' && ch <= '9';
}

bool isLetter(char ch) {
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

bool isSpacer(char ch) {
    return ch == ' ' || ch == '\n' || ch == '\t';
}

class LEXER {
    private:
    const char *_text;
    unsigned int _len;
    unsigned int _pos;
    char _ch;
    void nextChar() {
        this->_ch = (this->_pos >= this->_len ? 0 : this->_text[++this->_pos]);
        return;
    }
    void skipSpace() {
        while(this->_ch != 0 && isSpacer(this->_ch)) nextChar();
        return;
    }
    unsigned int skipNumber() {
        unsigned int res = 0;
        while(this->_ch != 0 && isNumber(this->_ch)) ++res, nextChar();
        return res;
    }
    unsigned int skipWord() {
        unsigned int res = 0;
        while(this->_ch != 0 && isLetter(this->_ch)) ++res, nextChar();
        return res;
    }
    const char *getPosString() const {
        return _text + _pos;
    }

    public:
    LEXER(const char *text, unsigned int len) : _text(text), _len(len), _pos() {
        this->_ch = (this->_pos >= this->_len ? 0 : this->_text[this->_pos]);
    }
    ~LEXER() {}
    TOKEN getNextToken() {
        while(this->_ch != 0) {
            if(isSpacer(this->_ch)) {
                skipSpace();
                continue;
            }
            if(isNumber(this->_ch)) {
                const char *pos = getPosString();
                return TOKEN(INTEGER, pos, skipNumber());
            }
            if(isLetter(this->_ch)) {
                const char *pos = getPosString();
                unsigned int len = skipWord();
                if(len == 2 && equalString("lt", pos, len)) return TOKEN(OPERATOR_LT);
                if(len == 2 && equalString("gt", pos, len)) return TOKEN(OPERATOR_GT);
                if(len == 2 && equalString("le", pos, len)) return TOKEN(OPERATOR_LE);
                if(len == 2 && equalString("ge", pos, len)) return TOKEN(OPERATOR_GE);
                if(len == 2 && equalString("eq", pos, len)) return TOKEN(OPERATOR_EQ);
                if(len == 3 && equalString("neq", pos, len)) return TOKEN(OPERATOR_NEQ);
                if(len == 3 && equalString("set", pos, len)) return TOKEN(OPERATOR_ASSIGN);
                if(len == 3 && equalString("ihu", pos, len)) return TOKEN(IHU);
                if(len == 3 && equalString("hor", pos, len)) return TOKEN(HOR);
                if(len == 3 && equalString("int", pos, len)) return TOKEN(VARIABLE_TYPE, pos, len);
                if(len == 4 && equalString("vars", pos, len)) return TOKEN(VARS);
                if(len == 5 && equalString("while", pos, len)) return TOKEN(WHILE);
                if(len == 5 && equalString("array", pos, len)) return TOKEN(VARIABLE_TYPE, pos, len);
                if(len == 6 && equalString("yosoro", pos, len)) return TOKEN(YOSORO);
                return TOKEN(VARIABLE_NAME, pos, len);
            }
            if(this->_ch == '+') {
                nextChar();
                return TOKEN(OPERATOR_PLUS);
            }
            if(this->_ch == '-') {
                nextChar();
                return TOKEN(OPERATOR_MINUS);
            }
            if(this->_ch == '(') {
                nextChar();
                return TOKEN(PAR_LEFT);
            }
            if(this->_ch == ')') {
                nextChar();
                return TOKEN(PAR_RIGHT);
            }
            if(this->_ch == '.') {
                nextChar();
                nextChar();
                return TOKEN(T_DOT);
            }
            if(this->_ch == ',') {
                nextChar();
                return TOKEN(T_COMMA);
            }
            if(this->_ch == ':') {
                nextChar();
                return TOKEN(T_COLON);
            }
            if(this->_ch == '[') {
                nextChar();
                return TOKEN(BRACKET_LEFT);
            }
            if(this->_ch == ']') {
                nextChar();
                return TOKEN(BRACKET_RIGHT);
            }
            if(this->_ch == '{') {
                nextChar();
                return TOKEN(BLOCK_LEFT);
            }
            if(this->_ch == '}') {
                nextChar();
                return TOKEN(BLOCK_RIGHT);
            }
            return TOKEN(T_NULL);
        }
        return TOKEN(T_EOF);
    }
};

class NODE {
    private:
    TOKEN _token;
    NODE **_list;
    bool _multi;
    unsigned int _siz, _msiz;
    bool _flag;
    int getConstantValue() {
        if(this->_token.getType() == INTEGER) return toInteger(this->_token.getValue(), this->_token.getLength());
        if(this->_token.getType() == VARS && this->_flag == 0) return this->_flag = 1;
        if(this->_token.getType() == BLOCK && this->_flag == 0) return this->_flag = 1;
        return 0;
    }
    int getUnaryValue() {
        if(this->_token.getType() == OPERATOR_PLUS) return +this->_list[0]->getValue();
        if(this->_token.getType() == OPERATOR_MINUS) return -this->_list[0]->getValue();
        if(this->_token.getType() == YOSORO) return printf("%d ", this->_list[0]->getValue()), 0;
        if(this->_token.getType() == VARIABLE_NAME) return getVar(this->_token.getValue(), this->_token.getLength())->getValue(this->_list[0]->getValue());
        if(this->_token.getType() == IHU && this->_flag == 0) return this->_flag = 1, this->_list[0]->getValue();
        if(this->_token.getType() == WHILE) return this->_list[0]->getValue();
        return 0;
    }
    int getBinValue() {
        if(this->_token.getType() == OPERATOR_PLUS) return this->_list[0]->getValue() + this->_list[1]->getValue();
        if(this->_token.getType() == OPERATOR_MINUS) return this->_list[0]->getValue() - this->_list[1]->getValue();
        if(this->_token.getType() == OPERATOR_LT) return this->_list[0]->getValue() < this->_list[1]->getValue();
        if(this->_token.getType() == OPERATOR_GT) return this->_list[0]->getValue() > this->_list[1]->getValue();
        if(this->_token.getType() == OPERATOR_LE) return this->_list[0]->getValue() <= this->_list[1]->getValue();
        if(this->_token.getType() == OPERATOR_GE) return this->_list[0]->getValue() >= this->_list[1]->getValue();
        if(this->_token.getType() == OPERATOR_EQ) return this->_list[0]->getValue() == this->_list[1]->getValue();
        if(this->_token.getType() == OPERATOR_NEQ) return this->_list[0]->getValue() != this->_list[1]->getValue();
        if(this->_token.getType() == OPERATOR_ASSIGN) return this->_list[0]->setValue(this->_list[1]->getValue());
        return 0;
    }
    int getMultiValue() {
        if(this->_token.getType() == T_COLON) {
            if(this->_siz == 1) {
                this->_list[0]->registerVar(0, 1);
            }
            else {
                this->_list[0]->registerVar(this->_list[1]->getValue(), this->_list[2]->getValue());
            }
            return 0;
        }
        if(this->_token.getType() == BLOCK) {
            while(this->_list[0]->getValue()) {
                for(unsigned int i = 1; i < this->_siz; i++) {
                    this->_list[i]->getValue();
                }
                this->_list[0]->setValue(0);
            }
            this->clearST();
        }
        if(this->_token.getType() == HOR) {
            if(this->_flag == 0) {
                this->_list[0]->setValue(this->_list[1]->getValue());
                this->_flag = 1;
            }
            return this->_list[0]->getValue() <= this->_list[2]->getValue();
        }
        return 0;
    }
    int registerVar(int s, int t) {
        VAR *p = new VAR(this->_token.getValue(), this->_token.getLength(), s, t);
        setVar(p);
        return 0;
    }
    int setValue(int v) {
        if(this->_token.getType() == VARIABLE_NAME) {
            VAR *p = getVar(this->_token.getValue(), this->_token.getLength());
            p->setValue(this->_list[0]->getValue(), v);
        }
        if(this->_token.getType() == HOR) {
            this->_list[0]->setValue(this->_list[0]->getValue() + 1);
        }
        return 0;
    }
    void clearST() {
        if(this->_siz == -1) return;
        for(unsigned int i = 0; i < this->_siz; i++) this->_list[i]->_flag = 0, this->_list[i]->clearST();
    }

    public:
    NODE(bool multi = 0) : _token(T_NULL), _list(), _siz(-1), _multi(multi), _msiz(), _flag() {
        if(this->_multi) this->_siz = 0;
    }
    NODE(TOKEN token) : _token(token), _list(), _siz(), _multi(), _msiz(), _flag() {}
    NODE(TOKEN token, NODE *expr0) : _token(token), _siz(1), _multi(), _msiz(1), _flag() {
        this->_list = new NODE *[this->_siz]();
        this->_list[0] = expr0;
    }
    NODE(TOKEN token, NODE *expr0, NODE *expr1) : _token(token), _siz(2), _multi(), _msiz(2), _flag() {
        this->_list = new NODE *[this->_siz]();
        this->_list[0] = expr0;
        this->_list[1] = expr1;
    }
    ~NODE() {
        if(this->_list)
            for(unsigned int i = 0; i < this->_siz; i++) delete this->_list[i];
    }
    int getValue() {
        if(this->_multi) return getMultiValue();
        switch(_siz) {
            case 0: return getConstantValue();
            case 1: return getUnaryValue();
            case 2: return getBinValue();
            default: break;
        }
        return 0;
    }
    void setToken(const TOKEN &token) {
        this->_token = token;
        return;
    }
    void push(NODE *expr0) {
        if(this->_siz >= this->_msiz) {
            unsigned int lmsiz = this->_msiz;
            this->_msiz = (this->_siz + 1) * 2;
            NODE **list = new NODE *[this->_msiz]();
            for(unsigned int i = 0; i < this->_siz; i++) list[i] = this->_list[i];
            if(this->_list) {
                delete[] this->_list;
            }
            this->_list = list;
        }
        this->_list[this->_siz++] = expr0;
        return;
    }
    int getSize() const {
        return this->_siz;
    }
};
class PARSER {
    private:
    LEXER _lexer;
    TOKEN _tok;
    void nextToken(TOKEN_TYPE typ) {
        if(this->_tok.getType() == typ) this->_tok = this->_lexer.getNextToken();
        return;
    }
    NODE *parserThird() {
        TOKEN token = this->_tok;
        if(token.getType() == INTEGER) {
            nextToken(INTEGER);
            return new NODE(token);
        }
        if(token.getType() == PAR_LEFT) {
            nextToken(PAR_LEFT);
            NODE *res = parserSecond();
            nextToken(PAR_RIGHT);
            return res;
        }
        if(token.getType() == VARIABLE_NAME) {
            nextToken(VARIABLE_NAME);
            NODE *res;
            if(this->_tok.getType() == BRACKET_LEFT) {
                nextToken(BRACKET_LEFT);
                res = parserSecond();
                nextToken(BRACKET_RIGHT);
            }
            else {
                res = new NODE();
            }
            return new NODE(token, res);
        }
        if(token.getType() == OPERATOR_PLUS || token.getType() == OPERATOR_MINUS) {
            nextToken(token.getType());
            return new NODE(token, parserThird());
        }

        return new NODE();
    }
    NODE *parserSecond() {
        NODE *res = parserThird();
        while(this->_tok.getType() != T_EOF) {
            TOKEN token = this->_tok;
            if(token.getType() == OPERATOR_PLUS || token.getType() == OPERATOR_MINUS) {
                nextToken(token.getType());
                res = new NODE(token, res, parserThird());
            }
            else {
                break;
            }
        }
        return res;
    }
    NODE *parserCall() {
        TOKEN token = this->_tok;
        if(token.getType() == YOSORO) {
            nextToken(YOSORO);
            return new NODE(token, parserSecond());
        }
        if(token.getType() == OPERATOR_ASSIGN) {
            nextToken(OPERATOR_ASSIGN);
            NODE *res = parserThird();
            nextToken(T_COMMA);
            return new NODE(token, res, parserSecond());
        }
        return new NODE();
    }
    NODE *parserVar() {
        NODE *res = new NODE(1);
        res->push(new NODE(this->_tok));
        nextToken(VARIABLE_NAME);
        res->setToken(this->_tok);
        nextToken(T_COLON);
        if(this->_tok.getLength() == 5) {
            nextToken(VARIABLE_TYPE);
            nextToken(BRACKET_LEFT);
            nextToken(VARIABLE_TYPE);
            nextToken(T_COMMA);
            res->push(new NODE(this->_tok));
            nextToken(INTEGER);
            nextToken(T_DOT);
            nextToken(T_DOT);
            res->push(new NODE(this->_tok));
            nextToken(INTEGER);
            nextToken(BRACKET_RIGHT);
        }
        else {
            nextToken(VARIABLE_TYPE);
        }
        return res;
    }
    NODE *parserIhu() {
        NODE *res;
        nextToken(IHU);
        TOKEN token = this->_tok;
        if(token.getType() == OPERATOR_LT || token.getType() == OPERATOR_GT || token.getType() == OPERATOR_LE || this->_tok.getType() == OPERATOR_GE || this->_tok.getType() == OPERATOR_EQ || token.getType() == OPERATOR_NEQ) {
            nextToken(token.getType());
            nextToken(T_COMMA);
            NODE *res1 = parserSecond();
            nextToken(T_COMMA);
            NODE *res2 = parserSecond();
            res = new NODE(token, res1, res2);
        }
        else {
            res = new NODE();
        }
        return new NODE(TOKEN(IHU), res);
    }
    NODE *parserHor() {
        NODE *res = new NODE(1);
        res->setToken(this->_tok);
        nextToken(HOR);
        res->push(parserSecond());
        nextToken(T_COMMA);
        res->push(parserSecond());
        nextToken(T_COMMA);
        res->push(parserSecond());
        return res;
    }
    NODE *parserWhile() {
        NODE *res;
        nextToken(WHILE);
        TOKEN token = this->_tok;
        if(token.getType() == OPERATOR_LT || token.getType() == OPERATOR_GT || token.getType() == OPERATOR_LE || this->_tok.getType() == OPERATOR_GE || this->_tok.getType() == OPERATOR_EQ || token.getType() == OPERATOR_NEQ) {
            nextToken(token.getType());
            nextToken(T_COMMA);
            NODE *res1 = parserSecond();
            nextToken(T_COMMA);
            NODE *res2 = parserSecond();
            res = new NODE(token, res1, res2);
        }
        else {
            res = new NODE();
        }
        return new NODE(TOKEN(WHILE), res);
    }
    NODE *parserFirst() {
        NODE *res = new NODE(1);
        res->setToken(TOKEN(BLOCK));
        while(this->_tok.getType() != T_EOF) {
            TOKEN token = this->_tok;
            if(token.getType() == VARS) {
                nextToken(VARS);
                res->push(new NODE(TOKEN(VARS)));
            }
            else if(token.getType() == IHU) {
                res->push(parserIhu());
            }
            else if(token.getType() == HOR) {
                res->push(parserHor());
            }
            else if(token.getType() == WHILE) {
                res->push(parserWhile());
            }
            else if(token.getType() == VARIABLE_NAME) {
                if(res->getSize() == 0) res->push(new NODE(TOKEN(BLOCK)));
                res->push(parserVar());
            }
            else if(token.getType() == T_COLON) {
                if(res->getSize() == 0) res->push(new NODE(TOKEN(BLOCK)));
                nextToken(T_COLON);
                res->push(parserCall());
            }
            else if(token.getType() == BLOCK_LEFT) {
                if(res->getSize() == 0) res->push(new NODE(TOKEN(BLOCK)));
                nextToken(BLOCK_LEFT);
                res->push(parserFirst());
                nextToken(BLOCK_RIGHT);
            }
            else {
                break;
            }
        }
        return res;
    }

    public:
    PARSER(LEXER lexer) : _lexer(lexer) {
        this->_tok = this->_lexer.getNextToken();
    }
    NODE *parser() {
        return parserFirst();
    }

    ~PARSER() {}
};

int calc(const char *exp, unsigned int len) {
    char *_exp = new char[len]();
    for(unsigned int i = 0; i < len; i++) _exp[i] = exp[i];
    int res = PARSER(LEXER(_exp, len)).parser()->getValue();
    delete[] _exp;
    return res;
}

}  // namespace CALCULATOR

#include <stdio.h>
#include <iostream>
using namespace std;
string str, str2;

int main() {
    while(getline(cin, str2)) {
        str += str2;
    }
    CALCULATOR::calc(str.c_str(), str.size());
    return 0;
}

后记

题解写了半个下午，继续学习变量类型去了。