phigon.cpp

#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
using namespace std;

/*
ifstream cin("in");
ofstream cout("out");
*/

enum Token
{
    tok_tab, tok_untab, tok_id, tok_num,
    tok_if, tok_while, tok_lparen, tok_rparen,
    tok_relop, tok_not, tok_and, tok_or,
    tok_assg, tok_plus, tok_minus,
    tok_star, tok_colon, tok_eof
};

enum Relop
{
    rel_eq, rel_neq,
    rel_geq, rel_leq,
    rel_lt, rel_gt
};

enum Opcode
{
    op_load, op_set, op_const,
    op_add, op_sub, op_mul, op_neg,
    op_eq, op_lt, op_gt,
    op_neq, op_leq, op_geq,
    op_or, op_and, op_not,
    op_jfalse, op_jump, op_end
};

const int base = 1000000000, blog = 9;

struct BigInt
{
    int d[70], hi;
    bool sign;

    BigInt() :
        hi(1), sign(false)
    {
        d[0] = 0;
    }

    BigInt(const char *s)
    {
        int l = strlen(s),
            p = (l - 1) / blog,
            k = (l % blog == 0 ? blog : l % blog);
        hi = p + 1;
        sign = false;
        for (int i = 0; i < hi; i++)
            d[i] = 0;
        for (int i = 0; i < l; i++, k--) {
            if (k == 0) {
                p--;
                k = blog;
            }
            d[p] = d[p] * 10 + s[i] - '0';
        }
    }

    void negate()
    {
        sign = !sign;
    }

    bool zero()
    {
        return hi == 1 && d[0] == 0;
    }

    int ucmp(BigInt &b)
    {
        if (hi < b.hi)
            return -1;
        if (hi > b.hi)
            return 1;
        for (int i = hi - 1; i >= 0; i--) {
            if (d[i] < b.d[i])
                return -1;
            if (d[i] > b.d[i])
                return 1;
        }
        return 0;
    }

    int cmp(BigInt& b)
    {
        if (zero() && b.zero())
            return 0;
        if (sign && b.sign)
            return -ucmp(b);
        if (sign && !b.sign)
            return -1;
        if (!sign && b.sign)
            return 1;
        return ucmp(b);
    }

    bool operator < (BigInt& b)
    {
        return cmp(b) < 0;
    }

    bool operator > (BigInt& b)
    {
        return cmp(b) > 0;
    }

    bool operator <= (BigInt& b)
    {
        return cmp(b) <= 0;
    }

    bool operator >= (BigInt& b)
    {
        return cmp(b) >= 0;
    }

    bool operator == (BigInt& b)
    {
        return cmp(b) == 0;
    }

    bool operator != (BigInt& b)
    {
        return cmp(b) != 0;
    }

    void uadd(BigInt &b)
    {
        int m = 0;
        for (int i = 0; i < hi || i < b.hi || m > 0; i++) {
            if (i == hi)
                d[hi++] = 0;
            if (i == b.hi)
                b.d[b.hi++] = 0;
            d[i] = m + d[i] + b.d[i];
            m = d[i] / base;
            d[i] %= base;
        }
    }

    void add(BigInt &b)
    {
        if (!sign && !b.sign)
            uadd(b);
        else if (!sign && b.sign)
            sign = usub(b);
        else if (sign && !b.sign)
            sign = !usub(b);
        else
            uadd(b);
    }

    bool usub(BigInt& b)
    {
        bool x = ucmp(b) < 0;
        int m = 0;
        for (int i = 0; i < hi || i < b.hi; i++) {
            if (i == hi)
                d[hi++] = 0;
            if (i == b.hi)
                b.d[b.hi++] = 0;
            if (!x)
                d[i] = d[i] - b.d[i] - m;
            else
                d[i] = b.d[i] - d[i] - m;
            if (d[i] < 0) {
                d[i] += base;
                m = 1;
            } else
                m = 0;
            if (i == hi)
                hi++;
        }

        while (hi > 1 && d[hi - 1] == 0)
            hi--;
        return x;
    }

    void sub(BigInt& b)
    {
        if (!sign && !b.sign)
            sign = usub(b);
        else if (sign && !b.sign)
            uadd(b);
        else if (!sign && b.sign)
            uadd(b);
        else
            sign = !usub(b);
    }

    BigInt mul(BigInt& b)
    {
        BigInt r;
        r.sign = sign ^ b.sign;
        r.hi = hi + b.hi;
        for (int i = 0; i < r.hi; i++)
            r.d[i] = 0;
        for (int j = 0; j < b.hi; j++) {
            int k = 0;
            for (int i = 0; i < hi; i++) {
                long long t = 1LL * d[i] * b.d[j] + r.d[i + j] + k;
                r.d[i + j] = t % base;
                k = (int) (t / base);
            }
            r.d[j + hi] = k;
        }
        while (r.hi > 1 && r.d[r.hi - 1] == 0)
            r.hi--;
        return r;
    }

    friend ostream& operator << (ostream& out, BigInt& b)
    {
        if (!b.zero() && b.sign)
            cout << '-';
        out << b.d[b.hi - 1];
        for (int i = b.hi - 2; i >= 0; i--)
            out << setw(blog) << setfill('0') << b.d[i];
        return out;
    }
};

struct Run
{
    vector<int> ops;
    vector<BigInt> cts;
    vector<BigInt> vars;
    vector<string> varnames;
    vector<int> varcodes;
    vector<bool> varused;
    BigInt istack[500];
    bool bstack[500];
    int len, top;
    int opc;
    int count[20], total;

    Run() :
        len(0), total(0)
    {
        for (int i = 0; i < 20; i++)
            count[i] = 0;
    }

    int get()
    {
        return ops.size();
    }

    int add_const(BigInt x)
    {
        cts.push_back(x);
        return cts.size() - 1;
    }

    void set_vars(int n)
    {
        vars.resize(n);
        varnames.resize(n);
        varcodes.resize(n);
        varused.resize(n);
    }

    int emitop(Opcode op)
    {
        ops.push_back(op);
        return len++;
    }

    int emitop(Opcode op, int x)
    {
        ops.push_back(op);
        len++;
        ops.push_back(x);
        return len++;
    }

    int save_jump()
    {
        ops.push_back(op_jfalse);
        int x = len++;
        ops.push_back(0);
        len++;
        return x;
    }

    void set_jump(int x, int j)
    {
        ops[x + 1] = j;
    }

    void exec()
    {
        top = opc = 0;
        bool g = true;
        //int p;
        bool z;
        while (g) {
            switch (ops[opc]) {
                case op_end:
                    g = false;
                    break;
                case op_add:
                    /*p = istack[top - 2] +
                        istack[top - 1];
                    istack[top - 2] = p;*/
                    istack[top - 2].add(istack[top - 1]);
                    top--;
                    opc++;
                    count[op_add]++;
                    total++;
                    break;
                case op_sub:
                    /*p = istack[top - 2] -
                        istack[top - 1];
                    istack[top - 2] = p;*/
                    istack[top - 2].sub(istack[top - 1]);
                    top--;
                    opc++;
                    count[op_sub]++;
                    total++;
                    break;
                case op_mul:
                    /*p = istack[top - 2] *
                        istack[top - 1];
                    istack[top - 2] = p;*/
                    istack[top - 2] = istack[top - 2].mul(istack[top - 1]);
                    top--;
                    opc++;
                    count[op_mul]++;
                    total++;
                    break;
                case op_load:
                    istack[top++] = vars[ops[opc + 1]];
                    opc += 2;
                    break;
                case op_set:
                    vars[ops[opc + 1]] = istack[--top];
                    varused[ops[opc + 1]] = true;
                    opc += 2;
                    count[op_set]++;
                    total++;
                    break;
                case op_const:
                    istack[top++] = cts[ops[opc + 1]];
                    opc += 2;
                    break;
                case op_neg:
                    /*istack[top - 1] = -istack[top - 1];*/
                    istack[top - 1].negate();
                    opc++;
                    count[op_neg]++;
                    total++;
                    break;
                case op_eq:
                    z = (istack[top - 2] ==
                         istack[top - 1]);
                    bstack[top - 2] = z;
                    top--;
                    opc++;
                    count[op_eq]++;
                    total++;
                    break;
                case op_neq:
                    z = (istack[top - 2] !=
                         istack[top - 1]);
                    bstack[top - 2] = z;
                    top--;
                    opc++;
                    count[op_neq]++;
                    total++;
                    break;
                case op_leq:
                    z = (istack[top - 2] <=
                         istack[top - 1]);
                    bstack[top - 2] = z;
                    top--;
                    opc++;
                    count[op_leq]++;
                    total++;
                    break;
                case op_geq:
                    z = (istack[top - 2] >=
                         istack[top - 1]);
                    bstack[top - 2] = z;
                    top--;
                    opc++;
                    count[op_geq]++;
                    total++;
                    break;
                case op_lt:
                    z = (istack[top - 2] <
                         istack[top - 1]);
                    bstack[top - 2] = z;
                    top--;
                    opc++;
                    count[op_lt]++;
                    total++;
                    break;
                case op_gt:
                    z = (istack[top - 2] >
                         istack[top - 1]);
                    bstack[top - 2] = z;
                    top--;
                    opc++;
                    count[op_gt]++;
                    total++;
                    break;
                case op_or:
                    z = (bstack[top - 2] ||
                         bstack[top - 1]);
                    bstack[top - 2] = z;
                    top--;
                    opc++;
                    count[op_or]++;
                    total++;
                    break;
                case op_and:
                    z = (bstack[top - 2] &&
                         bstack[top - 1]);
                    bstack[top - 2] = z;
                    top--;
                    opc++;
                    count[op_and]++;
                    total++;
                    break;
                case op_not:
                    bstack[top - 1] = !bstack[top - 1];
                    opc++;
                    count[op_not]++;
                    total++;
                    break;
                case op_jfalse:
                    if (!bstack[top - 1])
                        opc = ops[opc + 1];
                    else
                        opc += 2;
                    top--;
                    break;
                case op_jump:
                    opc = ops[opc + 1];
                    break;
            }
        }
    }

    void report_op(string s, int k)
    {
        if (k > 0)
            cout << s << k << endl;
    }

    void var_report()
    {
        for (int i = 0; i < (int) vars.size(); i++)
            if (varused[varcodes[i]])
                cout << varnames[i] << ": "
                     << vars[varcodes[i]] << endl;
    }


    void report()
    {
        report_op("!=: ", count[op_neq]);
        report_op("*: ", count[op_mul]);
        report_op("+: ", count[op_add]);
        report_op("-: ", count[op_sub] + count[op_neg]);
        report_op("<: ", count[op_lt]);
        report_op("<=: ", count[op_leq]);
        report_op("=: ", count[op_set]);
        report_op("==: ", count[op_eq]);
        report_op(">: ", count[op_gt]);
        report_op(">=: ", count[op_geq]);
        report_op("and: ", count[op_and]);
        report_op("not: ", count[op_not]);
        report_op("or: ", count[op_or]);
        cout << "total " << total << " operations" << endl;
        cout << endl;
        var_report();
    }
};

struct Lexer
{
    Token tok;
    Relop rel;
    map<string, int> vars;
    int c, ln, col, k,
        tabc, slen, xid,
        cvar;
    BigInt val;
    char str[500];

    Lexer()
    {
        cin >> noskipws;
        cvar = tabc = k = ln = col = 0;
        read();
    }

    int push_var()
    {
        string s(str);
        if (vars.find(s) == vars.end())
            vars[s] = cvar++;
        return vars[s];
    }

    void read()
    {
        if (c == '\n') {
            ln++;
            col = 0;
        }
        char cc;
        if (cin >> cc)
            c = cc;
        else
            c = -1;
        col++;
    }

    void read_tok()
    {
        if (tabc < k) {
            tabc += 4;
            tok = tok_tab;
            return;
        }
        if (tabc > k) {
            tabc -= 4;
            tok = tok_untab;
            return;
        }
        if (c == '\n')
            read();
        if (c < 0) {
            tok = tok_eof;
            return;
        }
        if (col == 1) {
            while (c == ' ')
                read();
            if (tabc != col - 1) {
                k = col - 1;
                read_tok();
                return;
            }
        }
        if (c == ' ' || c == '\r') {
            while (c == ' ' || c == '\r')
                read();
            return read_tok();
        }
        if (isalpha(c)) {
            slen = 0;
            while (isalpha(c)) {
                str[slen++] = c;
                read();
            }
            str[slen] = '\0';
            if (strcmp(str, "if") == 0)
                tok = tok_if;
            else if (strcmp(str, "while") == 0)
                tok = tok_while;
            else if (strcmp(str, "and") == 0)
                tok = tok_and;
            else if (strcmp(str, "or") == 0)
                tok = tok_or;
            else  if (strcmp(str, "not") == 0)
                tok = tok_not;
            else {
                tok = tok_id;
                xid = push_var();
            }
            return;
        }
        if (isdigit(c)) {
            slen = 0;
            //val = 0;
            while (isdigit(c)) {
                str[slen++] = c;
                //val = val * 10 + (c - '0');
                read();
            }
            str[slen] = '\0';
            val = BigInt(str);
            tok = tok_num;
            return;
        }
        switch (c) {
            case '(':
                tok = tok_lparen;
                read();
                return;
            case ')':
                tok = tok_rparen;
                read();
                return;
            case '+':
                tok = tok_plus;
                read();
                return;
            case '-':
                tok = tok_minus;
                read();
                return;
            case '*':
                tok = tok_star;
                read();
                return;
            case '<':
                read();
                tok = tok_relop;
                if (c == '=') {
                    rel = rel_leq;
                    read();
                } else
                    rel = rel_lt;
                return;
            case '>':
                read();
                tok = tok_relop;
                if (c == '=') {
                    rel = rel_geq;
                    read();
                } else
                    rel = rel_gt;
                return;
            case '=':
                read();
                if (c == '=') {
                    tok = tok_relop;
                    rel = rel_eq;
                    read();
                } else
                    tok = tok_assg;
                return;
            case '!':
                read();
                read();
                tok = tok_relop;
                rel = rel_neq;
                return;
            case ':':
                tok = tok_colon;
                read();
                return;
        }
    }
};

struct Parser
{
    Run r;
    Lexer l;

    void parse()
    {
        l.read_tok();
        program();
        r.emitop(op_end);
    }

    void program()
    {
        while (l.tok == tok_id ||
               l.tok == tok_if ||
               l.tok == tok_while) {
            if (l.tok == tok_id)
                assign();
            else if (l.tok == tok_if)
                if_stat();
            else
                while_stat();
        }
    }

    void assign()
    {
        int x = l.xid;
        l.read_tok(); //id
        l.read_tok(); //=
        expr(); //expr
        r.emitop(op_set, x);
    }

    void if_stat()
    {
        l.read_tok(); //if
        lexpr(); //expr
        int x = r.save_jump();
        l.read_tok(); //:
        l.read_tok(); //<tab>
        program();
        r.set_jump(x, r.get());
        l.read_tok(); //<untab>
    }

    void while_stat()
    {
        l.read_tok(); //while
        int g = r.get();
        lexpr(); //expr
        int x = r.save_jump();
        l.read_tok(); //:
        l.read_tok(); //<tab>
        program();
        r.emitop(op_jump, g);
        r.set_jump(x, r.get());
        l.read_tok(); //<untab>
    }

    void expr()
    {
        term();
        while (l.tok == tok_plus ||
               l.tok == tok_minus) {
            Token t = l.tok;
            l.read_tok();
            term();
            if (t == tok_plus)
                r.emitop(op_add);
            else
                r.emitop(op_sub);
        }
    }

    void term()
    {
        factor();
        while (l.tok == tok_star) {
            l.read_tok();
            factor();
            r.emitop(op_mul);
        }
    }

    void factor()
    {
        if (l.tok == tok_lparen) {
            l.read_tok();
            //expr();
            lexpr();
            l.read_tok();
        } else if (l.tok == tok_minus) {
            l.read_tok();
            factor();
            r.emitop(op_neg);
        } else if (l.tok == tok_num){
            l.read_tok();
            int x = r.add_const(l.val);
            r.emitop(op_const, x);
        } else if (l.tok == tok_id) {
            int x = l.push_var();
            l.read_tok();
            r.emitop(op_load, x);
        }
    }

    void lexpr()
    {
        lterm();
        while (l.tok == tok_or) {
            l.read_tok();
            lterm();
            r.emitop(op_or);
        }
    }

    void lterm()
    {
        lfactor();
        while (l.tok == tok_and) {
            l.read_tok();
            lfactor();
            r.emitop(op_and);
        }
    }

    void lfactor()
    {
        /*if (l.tok == tok_lparen) {
            l.read_tok(); // (
            lexpr();
            l.read_tok(); // )
        } else */
        if (l.tok == tok_not) {
            l.read_tok();
            lfactor();
            r.emitop(op_not);
        } else {
            expr();
            if (l.tok == tok_relop) {
                Relop rp = l.rel;
                l.read_tok();
                expr();
                switch (rp) {
                    case rel_eq:
                        r.emitop(op_eq);
                        break;
                    case rel_neq:
                        r.emitop(op_neq);
                        break;
                    case rel_leq:
                        r.emitop(op_leq);
                        break;
                    case rel_geq:
                        r.emitop(op_geq);
                        break;
                    case rel_lt:
                        r.emitop(op_lt);
                        break;
                    case rel_gt:
                        r.emitop(op_gt);
                        break;
                }
            }
        }
    }

    void run()
    {
        r.set_vars(l.cvar);
        int i = 0;
        map<string, int>::const_iterator it;
        for (it = l.vars.begin(); it != l.vars.end(); it++) {
            r.varnames[i] = (*it).first;
            r.varcodes[i] = (*it).second;
            i++;
        }
        r.exec();
    }

    void report()
    {
        r.report();
    }
};

int main()
{
    Parser p;
    p.parse();
    p.run();
    p.report();
    return 0;
}