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;
}