BOJ 7607:: List Calculator

print, 대입을 제외한 문법은 아래와 같습니다.

<num>은 정수 리터럴, <var>은 변수 이름입니다.

수식 평가가 조금 더러운데, 무한 수열을 다뤄야 하는 특성상 리스트 객체를 만들고 평가 결과가 리스트 객체를 반환하게 할 수가 없습니다. 따라서 평가 함수가 인덱스를 받고, 그 인덱스에 해당하는 원소를 반환하도록 하면 재귀함수 짜듯이 아주 편하게 구현할 수 있습니다.

#include<bits/stdc++.h>

using namespace std;
const unsigned INF = 2000000000;

enum class TokenType {
    IDENT,
    KEYWORD,
    INTEGER,
    OPSEP,
    ASSIGN,
    PLUS,
    MINUS,
    ASTER,
    SLASH,
    COLON,
    PAR_OPEN,
    PAR_CLOSE,
    BRA_OPEN,
    BRA_CLOSE,
};
struct Token {
    TokenType type;
    string value;
    Token(TokenType t, string v="") : type(t), value(v) {}
};

vector<Token> tokenize(string &s) {
    s.push_back(' ');
    TokenType cur_type = TokenType::OPSEP;
    string::iterator cur_begin;
    vector<Token> res;
    for (auto it = s.begin(); it != s.end(); it++) {
        if (cur_type == TokenType::OPSEP) {
            if (*it == ' ')
                continue;
            else if (isdigit(*it)) {
                cur_type = TokenType::INTEGER;
                cur_begin = it;
            }
            else if (isalpha(*it)) {
                cur_type = TokenType::IDENT;
                cur_begin = it;
            }
            else switch (*it) {
                case '=': res.push_back(Token(TokenType::ASSIGN)); break;
                case '+': res.push_back(Token(TokenType::PLUS)); break;
                case '-': res.push_back(Token(TokenType::MINUS)); break;
                case '*': res.push_back(Token(TokenType::ASTER)); break;
                case '/': res.push_back(Token(TokenType::SLASH)); break;
                case ':': res.push_back(Token(TokenType::COLON)); break;
                case '(': res.push_back(Token(TokenType::PAR_OPEN)); break;
                case ')': res.push_back(Token(TokenType::PAR_CLOSE)); break;
                case '[': res.push_back(Token(TokenType::BRA_OPEN)); break;
                case ']': res.push_back(Token(TokenType::BRA_CLOSE)); default:;
            }
        }
        else if (cur_type == TokenType::INTEGER && !isdigit(*it)) {
            res.push_back(Token(TokenType::INTEGER, string(cur_begin, it)));
            cur_type = TokenType::OPSEP;
            it--;
        }
        else if (cur_type == TokenType::IDENT && !isalpha(*it)) {
            string tok(cur_begin, it);
            if (tok == "print")
                res.push_back(Token(TokenType::KEYWORD, tok));
            else
                res.push_back(Token(TokenType::IDENT, tok));
            cur_type = TokenType::OPSEP;
            it--;
        }
    }
    return res;
}

struct Node;
using Vtit = vector<Token>::iterator;
using pNode = shared_ptr<Node>;
pNode variables[52];

inline int ord(char c) {return (c <= 'Z'? c - 'A' : c - 'a' + 26);}
inline bool is_elemop(TokenType type) {
    switch (type) {
        case TokenType::PLUS: case TokenType::MINUS: case TokenType::ASTER: case TokenType::SLASH:
            return true;
        default:;
    }
    return false;
}
inline char tttochar(TokenType type) {
    switch (type) {
        case TokenType::PLUS: return '+';
        case TokenType::MINUS: return '-';
        case TokenType::ASTER: return '*'; default:;
    }
    return '/';
}

struct Node {
    unsigned size;
    Node() : size(0) {}
    Node(unsigned n) : size(n) {}
    virtual int eval(unsigned idx) {return 0;}
};
struct IntLiteral : public Node {
    int value;
    IntLiteral(int v) : Node(1), value(v) {}
    virtual int eval(unsigned idx) {
        return this->value;
    }
};
struct Variable : public Node {
    char var_name;
    Variable (char c) : Node(variables[ord(c)]->size), var_name(c) {}
    virtual int eval(unsigned idx) {
        return variables[ord(this->var_name)]->eval(idx);
    }
};
struct Concat : public Node {
    pNode left, right;
    Concat(pNode l, pNode r) : Node(min(INF, l->size + r->size)), left(l), right(r) {}
    virtual int eval(unsigned idx) {
        if (idx < this->left->size)
            return left->eval(idx);
        return right->eval(idx - this->left->size);
    }
};
struct BinOp : public Node {
    char op;
    pNode left, right;
    BinOp(char op, pNode l, pNode r) : Node((l->size == 0 || r->size == 0)? 0 : max(l->size, r->size)), op(op), left(l), right(r) {}
    virtual int eval(unsigned idx) {
        int l = (idx < this->left->size? this->left->eval(idx) : this->left->eval(this->left->size - 1));
        int r = (idx < this->right->size? this->right->eval(idx) : this->right->eval(this->right->size - 1));
        switch (this->op) {
            case '+': return l + r;
            case '-': return l - r;
            case '*': return l * r;
        }
        return l / r;
    }
};
struct UnaryOp : public Node {
    char op;
    bool evaluated;
    int value;
    pNode operand;
    UnaryOp(char op_, pNode o) : Node(1), op(op_), evaluated(false), value(0), operand(o) {}
    virtual int eval(unsigned idx) {
        if (!this->evaluated) {
            this->value = this->operand->eval(0);
            for (unsigned i = 1; i < this->operand->size; i++)
                switch (this->op) {
                    case '+': this->value += this->operand->eval(i); break;
                    case '-': this->value -= this->operand->eval(i); break;
                    case '*': this->value *= this->operand->eval(i); break;
                    case '/': this->value /= this->operand->eval(i);
                }
            this->evaluated = true;
            this->operand = nullptr;
        }
        return this->value;
    }
};
struct Slicing : public Node {
    pNode operand;
    unsigned s, e;
    Slicing(pNode o, unsigned s_, unsigned e_) : Node(s_ < e_? e_ - s_ : 0), operand(o), s(s_), e(e_) {}
    virtual int eval(unsigned idx) {
        return this->operand->eval(this->s + idx);
    }
};

int parse_unsliced(Vtit it_begin, Vtit it_end, pNode &ast);
int parse_primary(Vtit it_begin, Vtit it_end, pNode &ast);
int parse_factor(Vtit it_begin, Vtit it_end, pNode &ast);
int parse_term(Vtit it_begin, Vtit it_end, pNode &ast);
int parse_seg(Vtit it_begin, Vtit it_end, pNode &ast);
int parse_list(Vtit it_begin, Vtit it_end, pNode &ast);

int parse_unsliced(Vtit it_begin, Vtit it_end, pNode &ast) {
    if (it_begin->type == TokenType::INTEGER) {
        ast = make_shared<IntLiteral>(stoi(it_begin->value));
        return 1;
    }
    if (it_begin->type == TokenType::IDENT) {
        ast = make_shared<Variable>((it_begin->value)[0]);
        return 1;
    }
    return 2 + parse_list(it_begin + 1, it_end, ast);
}
int parse_primary(Vtit it_begin, Vtit it_end, pNode &ast) {
    int cnt, s, e;
    pNode operand;
    cnt = parse_unsliced(it_begin, it_end, operand);
    while (it_begin + cnt != it_end && it_begin[cnt].type == TokenType::BRA_OPEN) {
        cnt++;
        s = (it_begin[cnt].type == TokenType::INTEGER? stoi(it_begin[cnt++].value) : 0);
        cnt++;
        e = (it_begin[cnt].type == TokenType::INTEGER? stoi(it_begin[cnt++].value) : operand->size);
        cnt++;
        operand = make_shared<Slicing>(operand, s, e);
    }
    ast = operand;
    return cnt;
}
int parse_factor(Vtit it_begin, Vtit it_end, pNode &ast) {
    if (!is_elemop(it_begin->type))
        return parse_primary(it_begin, it_end, ast);
    pNode operand;
    int cnt = 1 + parse_factor(it_begin + 1, it_end, operand);
    ast = make_shared<UnaryOp>(tttochar(it_begin->type), operand);
    return cnt;
}
int parse_term(Vtit it_begin, Vtit it_end, pNode &ast) {
    pNode left, right;
    int cnt = parse_factor(it_begin, it_end, left);
    while (it_begin + cnt != it_end
            && (it_begin[cnt].type == TokenType::ASTER || it_begin[cnt].type == TokenType::SLASH)) {
        TokenType type = it_begin[cnt].type;
        cnt++;
        cnt += parse_factor(it_begin + cnt, it_end, right);
        left = make_shared<BinOp>(tttochar(type), left, right);
    }
    ast = left;
    return cnt;
}
int parse_seg(Vtit it_begin, Vtit it_end, pNode &ast) {
    pNode left, right;
    int cnt = parse_term(it_begin, it_end, left);
    while (it_begin + cnt != it_end
            && (it_begin[cnt].type == TokenType::PLUS || it_begin[cnt].type == TokenType::MINUS)) {
        TokenType type = it_begin[cnt].type;
        cnt++;
        cnt += parse_term(it_begin + cnt, it_end, right);
        left = make_shared<BinOp>(tttochar(type), left, right);
    }
    ast = left;
    return cnt;
}
int parse_list(Vtit it_begin, Vtit it_end, pNode &ast) {
    pNode left, right;
    int cnt = parse_seg(it_begin, it_end, left);
    while (it_begin + cnt != it_end && it_begin[cnt].type == TokenType::COLON) {
        cnt++;
        cnt += parse_factor(it_begin + cnt, it_end, right);
        left = make_shared<Concat>(left, right);
    }
    ast = left;
    return cnt;
}


int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    pNode undefined_var = make_shared<Node>(INF);
    for (int i = 0; i < 52; i++)
        variables[i] = undefined_var;

    string s;
    while (true) {
        getline(cin, s);
        if (s == "#")
            break;
        vector<Token> tokens = tokenize(s);
        if (tokens[0].type == TokenType::KEYWORD) {
            pNode ast;
            parse_list(tokens.begin() + 1, tokens.end(), ast);
            for (unsigned i = 0; i < ast->size; i++) {
                cout << ast->eval(i);
                if (i != ast->size - 1)
                    cout << ':';
            }
            cout << endl;
        }
        else if (tokens[0].type == TokenType::IDENT) {
            pNode ast;
            parse_list(tokens.begin() + 2, tokens.end(), ast);
            variables[ord((tokens[0].value)[0])] = ast;
        }
    }

    return 0;
}