/* * ACM ICPC - CERC 2011 * * Sample solution: Stack Machine Executor (execute) * Author: Martin Kacer */ #include #include #include #define MAX_STACK 1000 #define MAX_PRGLEN 100000 #define MAX_NUM 1000000000 #define MIN_NUM -1000000000 #define MAX_QRYS 10000 #define ERR_PRES 1 #define ERR_WRONG 2 /* the following code is also used in the automatic judge for "program" */ /* (and that is the reason for all of the half-paranoic checks) */ typedef int NUM; typedef long long NUM2; typedef int INSFUN(NUM); INSFUN* progins[MAX_PRGLEN]; NUM progval[MAX_PRGLEN]; NUM stack[MAX_STACK]; int stkp, prglen; int check_max_stack() { if (stkp >= MAX_STACK) { /* should not happen in the "executor" problem; * exit here, so we may use this also as a judge for "program" */ fprintf(stderr, "stack overflow\n"); exit(ERR_WRONG); } return 0; } int ins_num(NUM par) { if (check_max_stack()) return 1; stack[stkp++] = par; return 0; } int ins_pop(NUM par) { if (stkp == 0) return 1; --stkp; return 0; } int ins_dup(NUM par) { if (check_max_stack()) return 1; stack[stkp] = stack[stkp-1]; ++stkp; return 0; } int ins_swp(NUM par) { int x; if (stkp < 2) return 1; x = stack[stkp-1]; stack[stkp-1] = stack[stkp-2]; stack[stkp-2] = x; return 0; } int ins_inv(NUM par) { if (stkp < 1) return 1; stack[stkp-1] = - stack[stkp-1]; return 0; } int ins_oper(NUM2 opfun(NUM2,NUM2)) { NUM2 x; if (stkp < 2) return 1; x = opfun(stack[stkp-2], stack[stkp-1]); if (x < MIN_NUM || x > MAX_NUM) return 1; stack[stkp-2] = (NUM) x; --stkp; return 0; } NUM2 op_add(NUM2 a, NUM2 b) { return a + b; } NUM2 op_sub(NUM2 a, NUM2 b) { return a - b; } NUM2 op_mul(NUM2 a, NUM2 b) { return a * b; } NUM2 op_div(NUM2 a, NUM2 b) { if (b == 0) return MAX_NUM + 1; if (b < 0) return op_div(-a, -b); return (a < 0) ? - (-a / b) : a / b; } NUM2 op_mod(NUM2 a, NUM2 b) { if (b == 0) return MAX_NUM + 1; if (b < 0) b = -b; return (a < 0) ? - (-a % b) : a % b; } int ins_add(NUM par) { return ins_oper(op_add); } int ins_sub(NUM par) { return ins_oper(op_sub); } int ins_mul(NUM par) { return ins_oper(op_mul); } int ins_div(NUM par) { return ins_oper(op_div); } int ins_mod(NUM par) { return ins_oper(op_mod); } int read_eoln() { int c = getchar(); if (c == '\r') c = getchar(); return (c == '\n') ? 0 : ERR_PRES; } int read_num(NUM *n) { NUM2 x = 0; int c = getchar(); if (!isdigit(c)) return ERR_PRES; while (isdigit(c)) { x = x * 10 + c - '0'; if (x > MAX_NUM) return ERR_PRES; c = getchar(); } ungetc(c, stdin); *n = (NUM) x; return 0; } int read_program() { prglen = 0; for (;;) { int c1 = getchar(); int c2 = getchar(); int c3 = getchar(); if (c1 == 'E' && c2 == 'N' && c3 == 'D') { return read_eoln(); } if (prglen == MAX_PRGLEN) return ERR_WRONG; if (c1 == 'N' && c2 == 'U' && c3 == 'M') { if (getchar() != ' ') return ERR_PRES; if (read_num(progval+prglen)) return ERR_PRES; if (read_eoln()) return ERR_PRES; progins[prglen++] = ins_num; continue; } if (read_eoln()) return ERR_PRES; if (c1 == 'P' && c2 == 'O' && c3 == 'P') { progins[prglen++] = ins_pop; continue; } if (c1 == 'D' && c2 == 'U' && c3 == 'P') { progins[prglen++] = ins_dup; continue; } if (c1 == 'S' && c2 == 'W' && c3 == 'P') { progins[prglen++] = ins_swp; continue; } if (c1 == 'I' && c2 == 'N' && c3 == 'V') { progins[prglen++] = ins_inv; continue; } if (c1 == 'A' && c2 == 'D' && c3 == 'D') { progins[prglen++] = ins_add; continue; } if (c1 == 'S' && c2 == 'U' && c3 == 'B') { progins[prglen++] = ins_sub; continue; } if (c1 == 'M' && c2 == 'U' && c3 == 'L') { progins[prglen++] = ins_mul; continue; } if (c1 == 'D' && c2 == 'I' && c3 == 'V') { progins[prglen++] = ins_div; continue; } if (c1 == 'M' && c2 == 'O' && c3 == 'D') { progins[prglen++] = ins_mod; continue; } return ERR_PRES; } } int run_program(NUM inp, NUM *outp) { int i; stack[0] = inp; stkp = 1; for (i = 0; i < prglen; ++i) { if (progins[i](progval[i])) { return ERR_WRONG; } } if (stkp != 1) { return ERR_WRONG; } *outp = stack[0]; return 0; } int read_quit() { if (getchar() != 'U') return ERR_PRES; if (getchar() != 'I') return ERR_PRES; if (getchar() != 'T') return ERR_PRES; if (read_eoln()) return ERR_PRES; return (getchar() == EOF) ? 0 : ERR_PRES; } int main() { for (;;) { int c, n; NUM xin, xout, q; if ((c = getchar()) == 'Q') { if (read_quit()) { return fprintf(stderr, "incorrect QUIT\n"); return ERR_PRES; } return 0; } ungetc(c, stdin); n = read_program(); if (n) { fprintf(stderr, "Error parsing program: %d\n", n); return n; } if (read_num(&q)) { fprintf(stderr, "Error parsing number of input values\n"); return ERR_PRES; } if (read_eoln()) { fprintf(stderr, "no newline\n"); return ERR_PRES; } if (q > MAX_QRYS) { fprintf(stderr, "too many queries\n"); return ERR_WRONG; } while (q-->0) { if (read_num(&xin)) { fprintf(stderr, "Error parsing input value\n"); return ERR_PRES; } if (read_eoln()) { fprintf(stderr, "no newline\n"); return ERR_PRES; } if (run_program(xin, &xout)) { printf("ERROR\n"); } else { printf("%d\n", xout); } } if (read_eoln()) { fprintf(stderr, "no newline after a test case\n"); return ERR_PRES; } printf("\n"); } }