#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAXLEN 256
#define TBLSIZE 64
#define PRINTERR 1

#define error(errorNum) { \
    err(errorNum); \
}

typedef enum {
    UNKNOWN, END, ENDFILE,INT, ID,ADDSUB,MULDIV,
    LOGICAL,INCDEC, ASSIGN,LPAREN, RPAREN, AND, OR, XOR
} TokenSet;

typedef enum {
    UNDEFINED, MISPAREN, NOTNUMID, NOTFOUND,
    RUNOUT, NOTLVAL, DIVZERO, SYNTAXERR
} ErrorType;

typedef struct {
    int val;
    char name[MAXLEN];
} Symbol;

typedef struct _Node {
    TokenSet data;
    int val;
    char lexeme[MAXLEN];
    struct _Node *left;
    struct _Node *right;
} BTNode;

void initTable(void);
char *getLexeme(void);
int match(TokenSet token);
BTNode *makeNode(TokenSet tok, const char *lexe);
void statement(void);
BTNode *assign_expr(void);
BTNode *assign_expr(void);
BTNode *or_expr(void);
BTNode *or_expr_tail(BTNode *left);
BTNode *xor_expr(void);
BTNode *xor_expr_tail(BTNode *left);
BTNode *and_expr(void);
BTNode *and_expr_tail(BTNode *left);
BTNode *addsub_expr(void);
BTNode *addsub_expr_tail(BTNode *left);
BTNode *muldiv_expr(void);
BTNode *muldiv_expr_tail(BTNode *left);
BTNode *unary_expr(void);
BTNode *factor(void);
void printPrefix(BTNode *root);

void advance(void);
TokenSet getToken(void);
int getval(char *str);
int setval(char *str, int val);
int evaluateTree(BTNode *root);
void err(ErrorType errorNum);
void freeTree(BTNode *root);
BTNode *expr_tail(BTNode *left);
BTNode *expr(void);
BTNode *term_tail(BTNode *left);
BTNode *term(void);

char lexeme[MAXLEN];
int cnt = 0;
int sbcount = 0;
Symbol table[TBLSIZE];
TokenSet curToken = UNKNOWN;

int main()
{
    initTable();
    while (1) {
        statement();
    }
    return 0;
}

void initTable(void)
{
    strcpy(table[0].name, "x");
    table[0].val = 0;
    strcpy(table[1].name, "y");
    table[1].val = 0;
    strcpy(table[2].name, "z");
    table[2].val = 0;
    sbcount = 3;
}

char *getLexeme(void)
{
    return lexeme;
}

int match(TokenSet token)
{
    if (curToken == UNKNOWN) advance();
    return token == curToken;
}


BTNode *makeNode(TokenSet tok, const char *lexe)
{
    BTNode *node = (BTNode*)malloc(sizeof(BTNode));
    strcpy(node->lexeme, lexe);
    node->data = tok;
    node->val = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void statement(void)
{
    BTNode *retp = NULL;
    if (match(END)) {
        advance();
    }
    else {
        retp = assign_expr();
        if (match(END)) {
            printPrefix(retp);
            printf("\n");
            evaluateTree(retp);

            cnt = 0;
            freeTree(retp);
            advance();
        }
        else error(SYNTAXERR);
    }
}

BTNode *assign_expr(void)
{
    BTNode *node = NULL;
    if(match(ID))
    {
        BTNode *left=NULL;
        left = makeNode(ID,getLexeme());
        advance();
        if(match(ASSIGN))
        {
            node = makeNode(ASSIGN, getLexeme());
            advance();
            node->left = left;
            node->right = assign_expr();
        }
        else if(match(END))
        {
            ungetc('\n',stdin);
            node=or_expr();
        }
        else
        {
            int len=0;
            len=strlen(left->lexeme);
            if(len>0)
            {
                for(int i=len-1;i>=0;i--)
                    ungetc(left->lexeme[i],stdin);
            }
            node=or_expr();
        }
    }
    else
        node=or_expr();
    return node;
}

BTNode *or_expr(void) {
    BTNode *node = xor_expr();
    return or_expr_tail(node);
}
BTNode *or_expr_tail(BTNode *left) {
    BTNode *node = NULL;

    if (match(OR)) {
        node = makeNode(OR, getLexeme());
        advance();
        node->left = left;
        node->right = xor_expr();
        return or_expr_tail(node);
    }
    else
        return left;
}

BTNode *xor_expr(void) {
    BTNode *node = and_expr();
    return xor_expr_tail(node);
}
BTNode *xor_expr_tail(BTNode *left) {
    BTNode *node = NULL;

    if (match(XOR)) {
        node = makeNode(XOR, getLexeme());
        advance();
        node->left = left;
        node->right = and_expr();
        return xor_expr_tail(node);
    }
    else
        return left;
}

BTNode *and_expr(void) {
    BTNode *node = addsub_expr();
    return and_expr_tail(node);
}
BTNode *and_expr_tail(BTNode *left) {
    BTNode *node = NULL;

    if (match(AND)) {
        node = makeNode(AND, getLexeme());
        advance();
        node->left = left;
        node->right = addsub_expr();
        return and_expr_tail(node);
    }
    else
        return left;
}

BTNode *addsub_expr(void) {
    BTNode *node = muldiv_expr();
    return addsub_expr_tail(node);
}
BTNode *addsub_expr_tail(BTNode *left) {
    BTNode *node = NULL;

    if (match(ADDSUB)) {
        node = makeNode(ADDSUB, getLexeme());
        advance();
        node->left = left;
        node->right = muldiv_expr();
        return addsub_expr_tail(node);
    }
    else
        return left;
}

BTNode *muldiv_expr(void) {
    BTNode *node = unary_expr();
    return muldiv_expr_tail(node);
}

BTNode *muldiv_expr_tail(BTNode *left) {
    BTNode *node = NULL;

    if (match(MULDIV)) {
        node = makeNode(MULDIV, getLexeme());
        advance();
        node->left = left;
        node->right = unary_expr();
        return muldiv_expr_tail(node);
    }
    else
        return left;
}

BTNode *unary_expr(void)
{
    BTNode *node = NULL;
    if(match(ADDSUB))
    {
        node = makeNode(ADDSUB, getLexeme());
        advance();
        node->right = unary_expr();
    }
    else
        node=factor();
    return node;
}

BTNode *factor(void) {
    BTNode *retp = NULL, *left = NULL;

    if (match(INT)) {
        retp = makeNode(INT, getLexeme());
        advance();
    }
    else if (match(ID)) {
        retp = makeNode(ID, getLexeme());
        advance();
    }
    else if(match(INCDEC))
    {
        left = makeNode(INCDEC, getLexeme());
        advance();
        retp = makeNode(ID, getLexeme());
        retp->left=left;
    }
    else if (match(LPAREN)) {
        advance();
        retp = assign_expr();
        if (match(RPAREN))
            advance();
        else error(MISPAREN);
    }
    else error(NOTNUMID);
    return retp;
}


void advance(void)
{
    curToken = getToken();
}

TokenSet getToken(void)
{
    int i = 0;
    char c = '\0';

    while ((c = fgetc(stdin)) == ' ' || c == '\t');

    if (isdigit(c)) {
        lexeme[0] = c;
        c = fgetc(stdin);
        i = 1;
        while (isdigit(c) && i < MAXLEN) {
            lexeme[i] = c;
            ++i;
            c = fgetc(stdin);
        }
        ungetc(c, stdin);
        lexeme[i] = '\0';
        return INT;
    }
    else if (c == '+' || c == '-') {
        lexeme[0] = c;
        c = fgetc(stdin);
        if (c == lexeme[0]) {
            lexeme[1] = c;
            lexeme[2] = '\0';
            return INCDEC;
        }
        else {
            ungetc(c, stdin);
            lexeme[1] = '\0';
            return ADDSUB;
        }
    }
    else if (c == '|' || c == '^'||c == '&' ) {
        lexeme[0] = c;
        lexeme[1] = '\0';
        return LOGICAL;
    }
    else if (c == '*' || c == '/') {
        lexeme[0] = c;
        lexeme[1] = '\0';
        return MULDIV;
    }
    else if (c == '\n') {
        lexeme[0] = '\0';
        return END;
    }
    else if (c == '=') {
        strcpy(lexeme, "=");
        return ASSIGN;
    }
    else if (c == '(') {
        strcpy(lexeme, "(");
        return LPAREN;
    }
    else if (c == ')') {
        strcpy(lexeme, ")");
        return RPAREN;
    }
    else if (isalpha(c) || c == '_') {
        lexeme[0] = c;
        c = fgetc(stdin);
        i = 1;
        while (isalpha(c) || isdigit(c) || c == '_') {
            lexeme[i] = c;
            ++i;
            c = fgetc(stdin);
        }
        ungetc(c, stdin);
        lexeme[i] = '\0';
        return ID;
    }
    else if (c == EOF) {
        return ENDFILE;
    }
    else return UNKNOWN;
}

int setval(char *str, int val)
{
    int i = 0;
    for (i = 0; i < sbcount; i++) {
        if (strcmp(str, table[i].name) == 0) {
            table[i].val = val;
            printf("MOV [%d] r%d\n", i*4, cnt-1);
            return val;
        }
    }

    if (sbcount >= TBLSIZE) error(RUNOUT);

    strcpy(table[sbcount].name, str);
    table[sbcount].val = val;
    printf("MOV [%d] r%d\n", sbcount*4, cnt-1);
    sbcount++;
    return val;
}


int getval(char *str)
{
    int i = 0;

    for (i = 0; i < sbcount; i++) {
        if (strcmp(str, table[i].name) == 0) {
            printf("MOV r%d [%d]\n", cnt, i*4);
            return table[i].val;
        }
    }
    error(NOTFOUND);
    return 0;
}

int evaluateTree(BTNode *root)
{
    int retval = 0, lv = 0, rv = 0;

    if (root != NULL) {
        switch (root->data) {
            case ID:
                retval = getval(root->lexeme);
                cnt++;
                break;
            case INT:
                retval = atoi(root->lexeme);
                printf("MOV r%d %d\n", cnt, retval);
                cnt++;
                break;
            case ASSIGN:
                rv = evaluateTree(root->right);
                retval = setval(root->left->lexeme, rv);
                break;
            case ADDSUB:
                lv = evaluateTree(root->left);
                rv = evaluateTree(root->right);
                if (strcmp(root->lexeme, "+") == 0) {
                    retval = lv + rv;
                    printf("ADD r%d r%d\n", cnt-2, cnt-1);
                    cnt--;
                }
                else if (strcmp(root->lexeme, "-") == 0) {
                    retval = lv - rv;
                    printf("SUB r%d r%d\n", cnt-2, cnt-1);
                    cnt--;
                }
                break;
            case MULDIV:
                lv = evaluateTree(root->left);
                rv = evaluateTree(root->right);
                if (strcmp(root->lexeme, "*") == 0) {
                    retval = lv * rv;
                    printf("MUL r%d r%d\n", cnt-2, cnt-1);
                    cnt--;
                }
                else if (strcmp(root->lexeme, "/") == 0) {
                    if (rv == 0) error(DIVZERO);
                    retval = lv / rv;
                    printf("DIV r%d r%d\n", cnt-2, cnt-1);
                    cnt--;
                }
                break;
            case INCDEC:
                lv = evaluateTree(root->left);
                rv = evaluateTree(root->right);
                if (strcmp(root->lexeme, "++") == 0) {
                    retval = lv + rv;
                    printf("ADD r%d r%d\n", cnt-2, cnt-1);
                    cnt--;
                    setval(root->left->lexeme, retval);
                }
                else if (strcmp(root->lexeme, "--") == 0) {
                    retval = lv - rv;
                    printf("SUB r%d r%d\n", cnt-2, cnt-1);
                    cnt--;
                    setval(root->left->lexeme, retval);
                }
                break;
            case LOGICAL://add
                lv = evaluateTree(root->left);
                rv = evaluateTree(root->right);
                if (strcmp(root->lexeme, "&") == 0) {
                    retval = lv & rv;
                    printf("AND r%d r%d\n", cnt-2, cnt-1);
                    cnt--;
                }
                else if (strcmp(root->lexeme, "|") == 0) {
                    retval = lv | rv;
                    printf("OR r%d r%d\n", cnt-2, cnt-1);
                    cnt--;
                }
                else if (strcmp(root->lexeme, "^") == 0) {
                    retval = lv ^ rv;
                    printf("XOR r%d r%d\n", cnt-2, cnt-1);
                    cnt--;
                }
                break;
            default:
                retval = 0;
        }
    }
    return retval;
}
void err(ErrorType errorNum)
{
    printf("EXIT 1\n");
    exit(0);
}
void freeTree(BTNode *root)
{
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

void printPrefix(BTNode *root) {
    if (root != NULL) {
        printf("%s ", root->lexeme);
        printPrefix(root->left);
        printPrefix(root->right);
    }
}