ex2.c

   1 #include "tcclib.h"
   2
   3 #define N 20
   4
   5 int nb_num;
   6 int tab[N];
   7 int stack_ptr;
   8 int stack_op[N];
   9 int stack_res[60];
  10 int result;
  11
  12 int find(int n, int i1, int a, int b, int op)
  13 {
  14     int i, j;
  15     int c;
  16
  17     if (stack_ptr >= 0) {
  18         stack_res[3*stack_ptr] = a;
  19         stack_op[stack_ptr] = op;
  20         stack_res[3*stack_ptr+1] = b;
  21         stack_res[3*stack_ptr+2] = n;
  22         if (n == result)
  23             return 1;
  24         tab[i1] = n;
  25     }
  26
  27     for(i=0;i<nb_num;i++) {
  28         for(j=i+1;j<nb_num;j++) {
  29             a = tab[i];
  30             b = tab[j];
  31             if (a != 0 && b != 0) {
  32
  33                 tab[j] = 0;
  34                 stack_ptr++;
  35
  36                 if (find(a + b, i, a, b, '+'))
  37                     return 1;
  38                 if (find(a - b, i, a, b, '-'))
  39                     return 1;
  40                 if (find(b - a, i, b, a, '-'))
  41                     return 1;
  42                 if (find(a * b, i, a, b, '*'))
  43                     return 1;
  44                 if (b != 0) {
  45                     c = a / b;
  46                     if (find(c, i, a, b, '/'))
  47                         return 1;
  48                 }
  49
  50                 if (a != 0) {
  51                     c = b / a;
  52                     if (find(c, i, b, a, '/'))
  53                         return 1;
  54                 }
  55
  56                 stack_ptr--;
  57                 tab[i] = a;
  58                 tab[j] = b;
  59             }
  60         }
  61     }
  62
  63     return 0;
  64 }
  65
  66 int main(int argc, char **argv)
  67 {
  68     int i, res, p;
  69
  70     if (argc < 3) {
  71         printf("usage: %s: result numbers...\n"
  72                "Try to find result from numbers with the 4 basic operations.\n", argv[0]);
  73         exit(1);
  74     }
  75
  76     p = 1;
  77     result = atoi(argv[p]);
  78     printf("result=%d\n", result);
  79     nb_num = 0;
  80     for(i=p+1;i<argc;i++) {
  81         tab[nb_num++] = atoi(argv[i]);
  82     }
  83
  84     stack_ptr = -1;
  85     res = find(0, 0, 0, 0, ' ');
  86     if (res) {
  87         for(i=0;i<=stack_ptr;i++) {
  88             printf("%d %c %d = %d\n",
  89                    stack_res[3*i], stack_op[i],
  90                    stack_res[3*i+1], stack_res[3*i+2]);
  91         }
  92         return 0;
  93     } else {
  94         printf("Impossible\n");
  95         return 1;
  96     }
  97 }