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