cal24point.c

用C写的一个算24点代码,使用逆波兰表达式的求值。

/* cal24.c
* given N integer numbers
* find one expression which produces value T using all
* the N numbers and {+,-,*,/} operators
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 4  /* number of cards    */
#define T 24 /* target solution    */
#define M 13 /* maximum card value */
#define STACK_SIZE (N+N-1)
#define EPS 1e-6
#define ADD M+1
#define SUB M+2
#define MUL M+3
#define DIV M+4

/* evaluate an expression in reverse Polish notation (RPN) */
double eval(int expr[])
{
    double oprnds[N],oprnd1,oprnd2;
    int top = -1,i,op;
    for(i = 0;i<STACK_SIZE;++i){
        op = expr[i];
        if(op<=M){
            oprnds[++top] = (double)op;
            continue;
        }
        oprnd1 = oprnds[top--];
        oprnd2 = oprnds[top--];
        switch(op){
        case ADD: oprnd1 += oprnd2; break;
        case SUB: oprnd1 -= oprnd2; break;
        case MUL: oprnd1 *= oprnd2; break;
        case DIV:
            if(oprnd2<EPS && oprnd2>-EPS) return 0.0;
            oprnd1 /= oprnd2;
        }
        oprnds[++top] = oprnd1;
    }
    return oprnds[top];
}

int succ(int expr[])
{
    double x = eval(expr);
    if(x>T-EPS && x<T+EPS) return 1;
    return 0;
}

/* just to make the expression more readable by human */
void printsolution(int expr[])
{
    double oprnds[N],oprnd1,oprnd2,result;
    int top = -1,i,op;
    char c;
    for(i = 0;i<STACK_SIZE;++i){
        op = expr[i];
        if(op<=M){
            oprnds[++top] = (double)op;
            continue;
        }
        oprnd1 = oprnds[top--];
        oprnd2 = oprnds[top--];
        switch(op){
        case ADD:
            c = '+';
            result = oprnd1 + oprnd2;
            break;
        case SUB:
            c = '-';
            result = oprnd1 - oprnd2;
            break;
        case MUL:
            c = '*';
            result = oprnd1 * oprnd2;
            break;
        case DIV:
            c = '/';
            result = oprnd1 / oprnd2;
        }
        printf("%.2f %c %.2f => %.2f\n",oprnd1,c,oprnd2,result);
        oprnds[++top] = result;
    }
}

/* update ret[] with next possible permutation of N cards */
int permute(int ret[])
{
    int orig[N],i,j = 1;
    for(i = 0;i<N-1;++i)
        if(ret[i]<ret[i+1]){
            j = 0;
            break;
        }
    if(j) return 0;
    for(i = 0;i<N;++i) orig[i] = ret[i];
    for(i = N-2;i>=0;--i)
        if(orig[i]<orig[i+1]) break;
    for(j = N-1;j>i;--j)
        if(orig[j]>orig[i]) break;
    ret[i] = orig[j];
    orig[j] = orig[i];
    for(j = i+1;j<N;++j)
        ret[j] = orig[N-j+i];
    return 1;
}

/* update ops[] with next possible operators */
int operators(int ops[])
{
    int i,j;
    for(i = N-1;i>=0;--i){
        if(ops[i]<DIV){
            ++ops[i];
            for(j = i+1;j<N-1;++j) ops[j] = ADD;
            return 1;
        }
    }
    return 0;
}

/* update expr[] with next possible expression in RPN */
int expressions(int expr[])
{
    if(expr[3]>M && expr[4]>M) return 0;
    if(expr[2]>M && expr[4]>M) expr[2]^=expr[3]^=expr[2]^=expr[3];
    else if(expr[2]>M) expr[4]^=expr[5]^=expr[4]^=expr[5];
    else if(expr[3]>M) expr[2]^=expr[3]^=expr[2]^=expr[3];
    else expr[3]^=expr[4]^=expr[3]^=expr[4];
    return 1;
}

int main(int argc,char *argv[])
{
    int opd[N],pmt[N],ops[N-1],expr[STACK_SIZE],i,succeed = 1;
    if(argc<N+1) exit(printf("Not enough arguments!\n"));
    for(i = 0;i<N;++i) opd[i] = atoi(argv[i+1]);
    for(i = 0;i<N;++i) pmt[i] = i;
    for(i = 0;i<N-1;++i) ops[i] = ADD;
    while(1){
        for(i = 0;i<N;++i) expr[i] = opd[pmt[i]];
        for(i = 0;i<N-1;++i) expr[N+i] = ops[i];
        if(succ(expr)) break;
        while(expressions(expr))
            if(succ(expr)) break;
        if(succ(expr)) break;
        if(!operators(ops)){
            if(!permute(pmt)){
                succeed = 0;
                break;
            }
            for(i = 0;i<N-1;++i) ops[i] = ADD;
        }
    }
    if(!succeed) exit(printf("Find no solutions!\n"));
    printsolution(expr);
}

/*
编译生成可执行文件cal24，测试结果如下：
[bohnanza:misc]$ ./cal24 3 3 8 8
8.00 / 3.00 => 2.67
3.00 - 2.67 => 0.33
8.00 / 0.33 => 24.00
[bohnanza:misc]$ ./cal24 5 5 1 5
1.00 / 5.00 => 0.20
5.00 - 0.20 => 4.80
4.80 * 5.00 => 24.00
[bohnanza:misc]$ ./cal24 4 4 10 10
10.00 * 10.00 => 100.00
100.00 - 4.00 => 96.00
96.00 / 4.00 => 24.00
[bohnanza:misc]$ ./cal24 3 7 3 7
3.00 / 7.00 => 0.43
0.43 + 3.00 => 3.43
7.00 * 3.43 => 24.00
[bohnanza:misc]$ ./cal24 1 2 3 4
2.00 + 1.00 => 3.00
3.00 + 3.00 => 6.00
4.00 * 6.00 => 24.00
[bohnanza:misc]$ ./cal24 7 7 7 7
Find no solutions!
*/