/* 14:6 */ #include #include #include typedef struct { int alpha[26]; int num; } ko_t; typedef struct { ko_t ko[100]; int n_ko; } expr_t; void print_expr(expr_t expr) { int i, k, j; for (i = 0; i < expr.n_ko; i++) { printf("%d", expr.ko[i].num); for (k = 0; k < 26; k++) { for (j = 0; j < expr.ko[i].alpha[k]; j++) { printf("%c", k + 'a'); } } printf("\n"); } } int douruiko(int a[], int b[]) { int i; for (i = 0; i < 26; i++) { if (a[i] != b[i]) return 0; } return 1; } int cmp(const ko_t *a, const ko_t *b) { int k; for (k = 0; k < 26; k++) { if (a->alpha[k] < b->alpha[k]) return 1; if (a->alpha[k] > b->alpha[k]) return -1; } return 0; } void normalize(expr_t *expr) { int i, j, k; int done[100]; expr_t new_expr; int keisu; for (i = 0; i < expr->n_ko; i++) { done[i] = 0; } new_expr.n_ko = 0; for (i = 0; i < expr->n_ko; i++) { if (!done[i]) { done[i] = 1; keisu = expr->ko[i].num; for (j = i + 1; j < expr->n_ko; j++) { if (douruiko(expr->ko[i].alpha, expr->ko[j].alpha)) { done[j] = 1; keisu += expr->ko[j].num; } } if (keisu != 0) { new_expr.ko[ new_expr.n_ko ].num = keisu; for (k = 0; k < 26; k++) { new_expr.ko[ new_expr.n_ko ].alpha[k] = expr->ko[i].alpha[k]; } (new_expr.n_ko)++; } } } expr->n_ko = new_expr.n_ko; for (i = 0; i < new_expr.n_ko; i++) { expr->ko[i].num = new_expr.ko[i].num; for (k = 0; k < 26; k++) { expr->ko[i].alpha[k] = new_expr.ko[i].alpha[k]; } } qsort(expr->ko, expr->n_ko, sizeof(ko_t), cmp); } int token(char str[], char tok[100][100]) { int i, j; int len = strlen(str); int in_num = 0; int n_tok = 0; int in_beki = 0; int beki; for (i = 0; i < len + 1; i++) { if (isdigit(str[i])) { if (in_num) { tok[n_tok][strlen(tok[n_tok]) + 1] = 0; tok[n_tok][strlen(tok[n_tok])] = str[i]; } else { tok[n_tok][0] = str[i]; tok[n_tok][1] = 0; in_num = 1; } } else if (str[i] == '^') { in_beki = 1; } else if (str[i] == 0) { if (in_num) { if (in_beki) { in_beki = 0; beki = atoi(tok[n_tok]); for (j = 0; j < beki; j++) { tok[n_tok-1+j][0] = tok[n_tok-1][0]; tok[n_tok-1+j][1] = 0; } n_tok += j - 1; } else { n_tok++; } in_num = 0; } } else if (isspace(str[i])) { if (in_num) { if (in_beki) { in_beki = 0; beki = atoi(tok[n_tok]); for (j = 0; j < beki; j++) { tok[n_tok-1+j][0] = tok[n_tok-1][0]; tok[n_tok-1+j][1] = 0; } n_tok += j - 1; } else { n_tok++; } in_num = 0; } continue; } else { if (in_num) { if (in_beki) { in_beki = 0; beki = atoi(tok[n_tok]); for (j = 0; j < beki; j++) { tok[n_tok-1+j][0] = tok[n_tok-1][0]; tok[n_tok-1+j][1] = 0; } n_tok += j - 1; } else { n_tok++; } } tok[n_tok][0] = str[i]; tok[n_tok][1] = 0; in_num = 0; n_tok++; } } return n_tok; } void mul(expr_t *a, expr_t b) { int i, j, k; expr_t r; r.n_ko = 0; for (i = 0; i < a->n_ko; i++) { for (j = 0; j < b.n_ko; j++) { r.ko[r.n_ko].num = a->ko[i].num * b.ko[j].num; for (k = 0; k < 26; k++) { r.ko[r.n_ko].alpha[k] = a->ko[i].alpha[k] + b.ko[j].alpha[k]; } (r.n_ko)++; } } a->n_ko = r.n_ko; for (i = 0; i < r.n_ko; i++) { a->ko[i].num = r.ko[i].num; for (k = 0; k < 26; k++) { a->ko[i].alpha[k] = r.ko[i].alpha[k]; } } } void add(expr_t *a, expr_t b) { int i, k; for (i = 0; i < b.n_ko; i++) { a->ko[ a->n_ko ].num = b.ko[i].num; for (k = 0; k < 26; k++) { a->ko[ a->n_ko ].alpha[k] = b.ko[i].alpha[k]; } (a->n_ko)++; } } void toexpr(char str[], ko_t *e) { int i; if (isdigit(str[0])) { e->num = atoi(str); for (i = 0; i < 26; i++) { e->alpha[i] = 0; } } else { e->num = 1; for (i = 0; i < 26; i++) { if (str[0] - 'a' == i) { e->alpha[i] = 1; } else { e->alpha[i] = 0; } } } } void one(expr_t *expr) { int k; expr->ko[ expr->n_ko ].num = 1; for (k = 0; k < 26; k++) { expr->ko[ expr->n_ko ].alpha[k] = 0; } expr->n_ko++; } expr_t *parse(char tok[100][100], int n_tok, expr_t *result) { int i, j, k, l; expr_t expr[100]; int d = 1; for (i = 0; i < 100; i++) { expr[i].n_ko = 0; } one(&(expr[d])); for (i = 0; i < n_tok; i++) { if (tok[i][0] == '+') { add(&(expr[d-1]), expr[d]); expr[d].n_ko = 0; one(&(expr[d])); } else if (tok[i][0] == '-') { add(&(expr[d-1]), expr[d]); expr[d].n_ko = 0; one(&(expr[d])); expr[d].ko[ expr[d].n_ko - 1].num = -expr[d].ko[ expr[d].n_ko - 1].num; } else if (tok[i][0] == '(') { expr[d+1].n_ko = 0; expr[d+2].n_ko = 0; one(&(expr[d+2])); d += 2; } else if (tok[i][0] == ')') { add(&(expr[d-1]), expr[d]); expr[d].n_ko = 0; d -= 2; mul(&(expr[d]), expr[d+1]); expr[d+1].n_ko = 0; } else { toexpr(tok[i], &(expr[d+1].ko[0])); expr[d+1].n_ko = 1; mul(&(expr[d]), expr[d+1]); expr[d+1].n_ko = 0; } #if 0 printf(">>%s\n", tok[i]); printf("-0--\n"); print_expr(expr[0]); printf("-1--\n"); print_expr(expr[1]); printf("-2--\n"); print_expr(expr[2]); printf("-3--\n"); print_expr(expr[3]); printf("-4--\n"); print_expr(expr[4]); printf("--\n\n"); #endif } add(&(expr[d-1]), expr[d]); #if 0 printf("Ans\n"); print_expr(expr[0]); #endif result->n_ko = expr[0].n_ko; for (i = 0; i < expr[0].n_ko; i++) { result->ko[i].num = expr[0].ko[i].num; for (k = 0; k < 26; k++) { result->ko[i].alpha[k] = expr[0].ko[i].alpha[k]; } } normalize(result); } int equals_expr(expr_t a, expr_t b) { int i; if (a.n_ko != b.n_ko) return 0; for (i = 0; i < a.n_ko; i++) { if (douruiko(a.ko[i].alpha, b.ko[i].alpha) && a.ko[i].num == b.ko[i].num) { continue; } else { return 0; } } return 1; } int main() { int i, j; char str[100]; char rtok[100][100]; int n_rtok; char ltok[100][100]; int n_ltok; expr_t rexpr, lexpr; freopen("expressions.txt", "r", stdin); while (1) { gets(str); if (str[0] == '.') break; n_rtok = token(str, rtok); #if 0 for (i = 0; i < n_rtok; i++) { printf(">>%s<<\n", rtok[i]); } printf("---\n"); #endif parse(rtok, n_rtok, &rexpr); while (1) { gets(str); if (str[0] == '.') { printf(".\n"); break; } n_ltok = token(str, ltok); /* printf("lex :"); for (i = 0; i < n_ltok; i++) { printf("%s ", ltok[i]); } printf("\n"); */ parse(ltok, n_ltok, &lexpr); /* printf(">>\n"); print_expr(lexpr); printf("<<\n"); */ if(equals_expr(rexpr, lexpr)) { printf("yes\n"); } else { printf("no\n"); } } } }