AOJ 0041

0041.c

/* AOJ 0041
 *
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041
 *
 */

#include <stdio.h>
#include <assert.h>


#define DEBUG 0

#define ADD 0
#define SUB 1
#define MUL 2


char* templates[5] = {
    "n,n,op,n,n,op,op,",
    "n,n,n,n,op,op,op,",
    "n,n,n,op,n,op,op,",
    "n,n,n,op,op,n,op,",
    "n,n,op,n,op,n,op,",
};


int gstack[10];
int gtop = 0;

int pop(){
    gtop -= 1;
    return gstack[gtop];
}

void push(int v){
    gstack[gtop] = v;
    gtop += 1;
}

void dumpstack(void){
    int i;
    printf("-----\n");
    for(i=0;i<gtop;i++){
        printf("stack[%d] = %d\n", i, gstack[i]);
    }
    printf("-----\n");
}

int calc(int op, int a, int b){
    switch(op){
        case ADD:
            return a+b;
            break;
        case SUB:
            return a-b;
            break;
        case MUL:
            return a*b;
            break;
        default:
            break;
    }
    assert(0);
}


int eval(char* t, int* ops, int* nums){
    int a;
    int b;
    while(*t){
        if(DEBUG){
            printf("%s\n", t);
            dumpstack();
        }
        if(*t == 'o'){
            t+=3;
            b = pop();
            a = pop();
            push(calc(*ops, a, b));
            ops++;
        }else{
            if(*t == 'n'){
                t+=2;
                push(*nums);
                nums++;
            }else{
                assert(0);
            }
        }
    }
    return pop();
}

void make_ops(int hash, int * ops){
    ops[0] = hash % 3;
    ops[1] = hash / 3 % 3;
    ops[2] = hash / 3 / 3  % 3;
}



int fact(int n){
    if(n==0){
        return 1;
    }else{
        return fact(n-1)*n;
    }
}

void make_nums(int len, int hash, int* input, int* output);
void make_nums(int len, int hash, int* input, int* output){
    int rest[len];
    int n,i;
    n = fact(len-1);

    if(len == 1){
        *output = *input; /*filling last item*/
    }else{
        for(i=0;i<hash/n;i++){
            *(rest+i)= *(input+i);
        }
        *output = input[hash/n];
        for(i=hash/n;i<len;i++){
            *(rest+i-1)= *(input+i);
        }
        make_nums(len - 1, hash%n, rest, output+1);
    }
}

void find(int *buf){
    int r;
    int i,j,k;
    int ops[3];
    int nums[4];
    for(i=0;i<81;i++){
        make_ops(i, ops);
        for(j=0;j<4*3*2*1;j++){
            make_nums(4, j, buf, nums);
            for(k=0;k<5;k++){
                r = eval(templates[k], ops, nums);
                if(r==10){
                    r = print(templates[k], ops, nums);
                    return;
                }
            }
        }
    }
    printf("0\n");
}

int main(){
    int buf[4];

    while(scanf("%d %d %d %d", buf, buf+1, buf+2, buf+3) == 4){
        if(buf[0] == 0 && buf[1] == 0 && buf[2] ==0 && buf[3] == 0){
            break;
        }
        if(DEBUG)
            printf("%d %d %d %d\n", buf[0], buf[1], buf[2], buf[3]);
        find(buf);
    }
    return 0;
}