用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! */