examples/ex2.c

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