#include <assert.h> #include <ctype.h> #include <stdio.h> #include <string.h> enum { TOK_END, TOK_NUM, TOK_VAR, TOK_LP, TOK_RP, TOK_BIN, TOK_UN }; enum { BIN_MUL, BIN_DIV, BIN_MOD, BIN_ADD, BIN_SUB, BIN_LT, BIN_LTE, BIN_GT, BIN_GTE, BIN_EQ, BIN_NE, BIN_AND, BIN_OR }; enum { UN_NEG, UN_NOT }; enum { ST_IF='f', ST_ELSE='l', ST_END='n', ST_WHILE='h', ST_SET='e', ST_PRINT='r', ST_NONE=0 }; const int bin_prec[] = { 5, 5, 5, 4, 4, 3, 3, 3, 3, 2, 2, 1, 0 }; const int max_prec = 6; struct stmt { int type; char *expr; struct stmt *blocks[2]; int varidx; struct stmt *next; }; struct stmt statements[50]; int stmts_used; int vars[26]; // --------------------------------------------------------------------------- // Expression parsing // --------------------------------------------------------------------------- int token_type, token_value; char *line_ptr; void set_token(int type, int value, int num_chars) { token_type = type; token_value = value; line_ptr += num_chars; } void next_token() { while (isspace(*line_ptr)) ++line_ptr; if (!*line_ptr) { set_token(TOK_END, 0, 0); } else if (isdigit(*line_ptr)) { set_token(TOK_NUM, 0, 0); while (isdigit(*line_ptr)) { token_value = token_value * 10 + *line_ptr - '0'; ++line_ptr; } } else if (islower(*line_ptr)) { set_token(TOK_VAR, *line_ptr - 'a', 1); } else { int op = *line_ptr; if ((op == '<' || op == '>') && line_ptr[1] == '=') op += 128; if ((op == '-' || op == '!') && (token_type != TOK_NUM && token_type != TOK_VAR && token_type != TOK_RP)) op += 128; switch (op) { case '(': set_token(TOK_LP, 0, 1); break; case ')': set_token(TOK_RP, 0, 1); break; case '*': set_token(TOK_BIN, BIN_MUL, 1); break; case '/': set_token(TOK_BIN, BIN_DIV, 1); break; case '%': set_token(TOK_BIN, BIN_MOD, 1); break; case '+': set_token(TOK_BIN, BIN_ADD, 1); break; case '=': set_token(TOK_BIN, BIN_EQ, 2); break; case '&': set_token(TOK_BIN, BIN_AND, 2); break; case '|': set_token(TOK_BIN, BIN_OR, 2); break; case '<': set_token(TOK_BIN, BIN_LT, 1); break; case '>': set_token(TOK_BIN, BIN_GT, 1); break; case '-': set_token(TOK_BIN, BIN_SUB, 1); break; case '!': set_token(TOK_BIN, BIN_NE, 2); break; // Alternate ops: < or > with =, unary - or ! case '<'+128: set_token(TOK_BIN, BIN_LTE, 2); break; case '>'+128: set_token(TOK_BIN, BIN_GTE, 2); break; case '-'+128: set_token(TOK_UN, UN_NEG, 1); break; case '!'+128: set_token(TOK_UN, UN_NOT, 1); break; default: assert(!"parse error"); } } } int eval_expr(int min_prec) { int result, unop; switch (token_type) { case TOK_LP: next_token(); result = eval_expr(0); assert(token_type == TOK_RP); next_token(); break; case TOK_UN: unop = token_value; next_token(); result = eval_expr(max_prec); switch (unop) { case UN_NEG: result = -result; break; case UN_NOT: result = !result; break; default: assert(!"parse error"); } break; case TOK_NUM: result = token_value; next_token(); break; case TOK_VAR: result = vars[token_value]; next_token(); break; default: assert(!"parse error"); } while (token_type == TOK_BIN && bin_prec[token_value] >= min_prec) { int op = token_value; next_token(); int rhs = eval_expr(bin_prec[op] + 1); switch (op) { case BIN_MUL: result = result * rhs; break; case BIN_DIV: result = result / rhs; break; case BIN_MOD: result = result % rhs; break; case BIN_ADD: result = result + rhs; break; case BIN_SUB: result = result - rhs; break; case BIN_LT: result = result < rhs; break; case BIN_LTE: result = result <= rhs; break; case BIN_GT: result = result > rhs; break; case BIN_GTE: result = result >= rhs; break; case BIN_EQ: result = result == rhs; break; case BIN_NE: result = result != rhs; break; case BIN_AND: result = result && rhs; break; case BIN_OR: result = result || rhs; break; default: assert(!"unexpected bin op"); } } return result; } int eval_expr_str(char *expr) { token_type = TOK_END; line_ptr = expr; next_token(); return eval_expr(0); } // --------------------------------------------------------------------------- // Statement parsing // --------------------------------------------------------------------------- char raw_input[5100]; int raw_input_used; int lines_remain; char *stmt_line_ptr; int stmt_type; struct stmt* parse_statement(); void next_line() { if (lines_remain) { --lines_remain; stmt_line_ptr = &raw_input[raw_input_used]; scanf("%[^\n]%*c", stmt_line_ptr); raw_input_used += strlen(stmt_line_ptr) + 1; while (isspace(*stmt_line_ptr)) ++stmt_line_ptr; stmt_type = stmt_line_ptr[1]; } else { stmt_type = ST_NONE; } } struct stmt* parse_block() { struct stmt *result = 0; struct stmt **next = &result; while (stmt_type != ST_NONE && stmt_type != ST_ELSE && stmt_type != ST_END) { *next = parse_statement(); next = &(*next)->next; } return result; } struct stmt* parse_statement() { struct stmt *result = &statements[stmts_used++]; result->type = stmt_type; switch (stmt_type) { case ST_IF: result->expr = stmt_line_ptr + 2; next_line(); result->blocks[0] = parse_block(); if (stmt_type == ST_ELSE) { next_line(); result->blocks[1] = parse_block(); } break; case ST_WHILE: result->expr = stmt_line_ptr + 5; next_line(); result->blocks[0] = parse_block(); break; case ST_SET: stmt_line_ptr += 3; while (isspace(*stmt_line_ptr)) ++stmt_line_ptr; result->varidx = stmt_line_ptr[0] - 'a'; ++stmt_line_ptr; while (isspace(*stmt_line_ptr)) ++stmt_line_ptr; result->expr = stmt_line_ptr + 1; break; case ST_PRINT: result->expr = stmt_line_ptr + 5; break; default: assert(!"parse error"); } next_line(); return result; } // --------------------------------------------------------------------------- // Execution // --------------------------------------------------------------------------- void run_block(struct stmt *stmt) { while (stmt) { switch (stmt->type) { case ST_IF: if (eval_expr_str(stmt->expr)) run_block(stmt->blocks[0]); else run_block(stmt->blocks[1]); break; case ST_WHILE: while (eval_expr_str(stmt->expr)) run_block(stmt->blocks[0]); break; case ST_SET: vars[stmt->varidx] = eval_expr_str(stmt->expr); break; case ST_PRINT: printf("%d\n", eval_expr_str(stmt->expr)); break; } stmt = stmt->next; } } int main() { for (;;) { scanf("%d ", &lines_remain); if (!lines_remain) break; memset(vars, 0, sizeof(vars)); memset(statements, 0, sizeof(statements)); stmts_used = raw_input_used = 0; next_line(); struct stmt *prog = parse_block(); run_block(prog); } }