#include #include #define MAX_VARS 107 #define MAX_EQS 107 #define MAX_LINE_LENGTH 100 struct var_hash_elt { char *var_name; unsigned var_value; }; struct expr_hash_elt { char operator; unsigned left_val, right_val; unsigned expr_value; }; struct var_hash_elt var_hash[MAX_VARS]; struct expr_hash_elt expr_hash[MAX_EQS]; unsigned n_vars, n_values; static struct var_hash_elt * get_var (char *var_name) { unsigned hash = 0; char *t; for (t = var_name; *t; t++) hash = (76 * hash + *t) % MAX_VARS; while (var_hash[hash].var_name && strcmp (var_hash[hash].var_name, var_name)) { hash++; if (hash == MAX_VARS) hash = 0; } if (!var_hash[hash].var_name) { var_hash[hash].var_name = strdup (var_name); var_hash[hash].var_value = n_values++; n_vars++; } return var_hash + hash; } static struct expr_hash_elt * get_expr (unsigned left_val, char op, unsigned right_val) { unsigned hash, t; if (left_val > right_val) { t = left_val; left_val = right_val; right_val = t; } hash = (76 * left_val + 777 * op + right_val) % MAX_EQS; while (expr_hash[hash].operator && (expr_hash[hash].operator != op || expr_hash[hash].left_val != left_val || expr_hash[hash].right_val != right_val)) { hash++; if (hash == MAX_EQS) hash = 0; } if (!expr_hash[hash].operator) { expr_hash[hash].operator = op; expr_hash[hash].left_val = left_val; expr_hash[hash].right_val = right_val; expr_hash[hash].expr_value = n_values++; } return expr_hash + hash; } static int id_char (char ch) { return (('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z') || ch == '_'); } static void skip_blanks (char **buffer) { while (**buffer == ' ') (*buffer)++; } static struct var_hash_elt * parse_var (char **buffer) { char *var_end, ech; struct var_hash_elt *ret; skip_blanks (buffer); for (var_end = *buffer; id_char (*var_end); var_end++) continue; ech = *var_end; *var_end = 0; ret = get_var (*buffer); *var_end = ech; *buffer = var_end; skip_blanks (buffer); return ret; } static char parse_eq (char *buffer, struct var_hash_elt **tgt, unsigned *left_val, unsigned *right_val) { char ret; skip_blanks (&buffer); if (!*buffer) return ' '; *tgt = parse_var (&buffer); if (*buffer++ != '=') abort (); *left_val = parse_var (&buffer)->var_value; if (*buffer == ';') ret = '='; else { ret = *buffer++; if (ret != '+' && ret != '*') abort (); *right_val = parse_var (&buffer)->var_value; } if (*buffer++ != ';') abort (); skip_blanks (&buffer); if (*buffer) abort (); return ret; } int main(void) { char buffer[MAX_LINE_LENGTH]; while (gets (buffer)) { unsigned left_val, right_val; struct var_hash_elt *tgt; char eq_type = parse_eq (buffer, &tgt, &left_val, &right_val); switch (eq_type) { case '*': case '+': tgt->var_value = get_expr (left_val, eq_type, right_val)->expr_value; break; case '=': tgt->var_value = left_val; break; default: break; } } printf ("%d\n", n_values - n_vars); return 0; }