http://acm.pku.edu.cn/JudgeOnline/problem?id=1100
Код:
#include <stdio.h> #include <string.h> #include <ctype.h> #include <stdlib.h> #define MAX_STLEN 80 typedef enum {no_type, plus, minus, times} op_type; #define DEBUG_MODE 0 #define COUNTING_MODE 0 #define SUCCESS -1 #define NO_SUCCESS 0 char s[MAX_STLEN + 2], sol_string[MAX_STLEN + 2]; op_type act_d[MAX_STLEN], valid_d[MAX_STLEN]; int no_distr_found; int no_digits; int val_wanted; typedef struct { int val; struct parsing_tree_t *addr; } parsing_tree_el_t; struct parsing_tree_t { int no_branches; parsing_tree_el_t branches[MAX_STLEN]; op_type ops[MAX_STLEN]; }; struct parsing_tree_t *ptree; struct parsing_tree_t *construct_ptree(char *s, int *newpos) { int arg, j; int i; struct parsing_tree_t *pt; char *tmp[sizeof(char *)]; int pos = 0; pt = (struct parsing_tree_t *) malloc(sizeof(struct parsing_tree_t)); pt->no_branches = 0; while (s[pos] == ' ') pos++; for (i = pos; i < strlen(s); i++) { if (s[i] == '(') { pt->branches[pt->no_branches].addr = construct_ptree(s + i + 1, &j); pt->no_branches++; i += j + 1; } else if (isdigit((int)s[i])) { no_digits++; arg = strtol(s + i, tmp, 10); j = *tmp - s - i; pt->branches[pt->no_branches].val = arg; pt->branches[pt->no_branches].addr = NULL; i += j - 1; pt->no_branches++; } else if (s[i] == ')') {*newpos = i; return pt;} } /* for */ return pt; } void show(struct parsing_tree_t *pt, int k) { int i, j; for (i = 0; i < pt->no_branches; i++) { char c = pt->ops[i] == plus ? '+' : pt->ops[i] == minus ? '-' : pt->ops[i] == times ? '*' : '?'; for (j = 0; j < k; j++) printf(" "); printf("%d: ", i); if (pt->branches[i].addr == NULL) { printf("%d / %c\n", pt->branches[i].val, c); } else { printf("node-> (%c)\n", c); show(pt->branches[i].addr, k + 2); } } } void construct_sol_string(struct parsing_tree_t *pt, char *begin) { int i; for (i = 0; i < pt->no_branches; i++) { char c = pt->ops[i] == plus ? '+' : pt->ops[i] == minus ? '-' : pt->ops[i] == times ? '*' : '?'; if (pt->branches[i].addr == NULL) { sprintf(begin + strlen(begin), "%d", pt->branches[i].val); } else { char tmps[MAX_STLEN + 2]; strcpy(tmps, ""); sprintf(begin + strlen(begin),"("); construct_sol_string(pt->branches[i].addr, tmps); sprintf(begin + strlen(begin),"%s)", tmps); } if (i < pt->no_branches - 1) sprintf(begin + strlen(begin), "%c", c); } } int distribute_ops(struct parsing_tree_t *pt, op_type ops[MAX_STLEN], int pos) { int i = pos, j = 0; for (j = 0; j < pt->no_branches; j++) { if (j < pt->no_branches - 1) pt->ops[j] = ops[i++]; if (pt->branches[j].addr != NULL) i = distribute_ops(pt->branches[j].addr, ops, i); } return i; } int parse_ptree(struct parsing_tree_t *pt) { int i, res; res = (pt->branches[0].addr == NULL) ? pt->branches[0].val : parse_ptree(pt->branches[0].addr); for (i = 1; i < pt->no_branches; i++) { if (pt->ops[i - 1] == plus) res += (pt->branches[i].addr == NULL) ? pt->branches[i].val : parse_ptree(pt->branches[i].addr); else if (pt->ops[i - 1] == times) res *= (pt->branches[i].addr == NULL) ? pt->branches[i].val : parse_ptree(pt->branches[i].addr); else if (pt->ops[i - 1] == minus) res -= (pt->branches[i].addr == NULL) ? pt->branches[i].val : parse_ptree(pt->branches[i].addr); } return res; } int try_all_distr (op_type arr[], int beg_pos) { op_type curr_op; for (curr_op = plus; curr_op <= times; curr_op++) { arr[beg_pos] = curr_op; if (beg_pos < no_digits - 2) { if (try_all_distr(arr, beg_pos + 1) == SUCCESS) return SUCCESS; } else { int result; distribute_ops(ptree, arr, 0); #if DEBUG_MODE show(ptree, 0); #endif result = parse_ptree(ptree); #if DEBUG_MODE printf("val_wanted: %d, result: %d\n", val_wanted, result); #endif if (result == val_wanted) { strcpy(sol_string, ""); construct_sol_string(ptree, sol_string); printf("%d=%s\n", val_wanted, sol_string); no_distr_found++; #if !COUNTING_MODE return SUCCESS; #endif #if DEBUG_MODE printf("\nYes!\n"); #endif } } } return NO_SUCCESS; } int main(int argc, char *argv[]) { int k, case_counter = 0; FILE *f = stdin; char *st; char *tmp[sizeof(char *)]; op_type arr[MAX_STLEN + 2]; while (1) { fgets(s, MAX_STLEN + 2, f); #if DEBUG_MODE printf(s); #endif if (!strcmp(s, "0\n")) break; st = s; val_wanted = strtol(s, tmp, 10); st = *tmp; while (*st++ != '=') ; no_digits = 0; no_distr_found = 0; ptree = construct_ptree(st, &k); printf("Equation #%d:\n", ++case_counter); #if COUNTING_MODE (void) try_all_distr(arr, 0); if (no_digits == 1 && no_distr_found == 3) no_distr_found = 1; printf("%d possibilities\n", no_distr_found); #else if (try_all_distr(arr, 0) == NO_SUCCESS) printf("Impossible\n"); #endif printf("\n"); if (feof(f)) break; } fclose(f); return 0; } struct parsing_tree_t *copy_ptree(struct parsing_tree_t *pt) { int i; struct parsing_tree_t *p = (struct parsing_tree_t *) malloc(sizeof(struct parsing_tree_t)); p->no_branches = pt->no_branches; for (i = 0; i < pt->no_branches; i++) { p->branches[i].val = pt->branches[i].val; if (pt->branches[i].addr == NULL) p->branches[i].addr = NULL; else p->branches[i].addr = copy_ptree(pt->branches[i].addr); } return p; }