- 论坛徽章:
- 0
|
主要是使用逆波兰表达式的求值。欢迎测试和指正!
- /* 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);
- }
复制代码 |
|