c语言的运算符号数组替代

2022-08-01 综合 66阅读

运算符号字符只是一个记号,最后由程序翻译就好了。我看楼主问题似乎和计算24点的问题有点相似,我正好写了一个,就是全搜索,计算所有可能的解,式子表现为一颗二叉树,叶子节点是数,其它节点代表运算符。代码如下,仅供参考:

#include 
#include 

/*
 * game to get 24, give n, four symbols ( + - * / )
 * will max f(n) = 3**(n-1) * n! * (n-1)! values
 * f(4) = 3888       f(5) = 233280
 * f(6) = 20995200   f(7) = 2645395200
 * so maybe 6 or 7 is the limited.
 */

#define LMX_ABS(a)   ((a)<0?(-(a)):(a))
bool DblEqual_L(double a, double b)
{
    return LMX_ABS(a-b) < 0.0000001;
}

#define MAXN 6
#define MAX_SAVE 128

int n = 4, aim = 24;
int v[MAXN] = { 5, 3, 7, 8 };
char symbols[8] = "+-_*/?";

struct Node
{
    double val;
    int syb;
    struct Node *l, *r, *p;
};

Node node[(MAXN*2-1) * MAX_SAVE], curr[MAXN*2-1];
Node *root[MAX_SAVE];
bool used[MAXN*2-1];

int i_save, i_exist, i_base;

void DfsCopy_L(Node *q, Node *p)
{
    if (p->l != NULL){
        node[i_base].p = q;
        node[i_base].val = p->l->val;
        node[i_base].syb = p->l->syb;
        q->l = &node[i_base];
        i_base++;
        node[i_base].p = q;
        node[i_base].val = p->r->val;
        node[i_base].syb = p->r->syb;
        q->r = &node[i_base];
        i_base++;
        DfsCopy_L(q->l, p->l);
        DfsCopy_L(q->r, p->r);
    }
}
void Save_L(Node *p)
{
    i_base = i_save*(MAXN*2-1);
    root[i_save] = &node[i_base];
    Node *q = root[i_save];
    q->val = p->val;
    q->syb = p->syb;
    i_base++;
    DfsCopy_L(q, p);
    i_save++;
}

void Print_L(Node *p)
{
    if (p->syb < 0) printf("%d", (int)(p->val+0.0001));
    else if (p->syb == 2 || p->syb == 5){
        printf("( ");
        Print_L(p->r);
        printf(" %c ", symbols[p->syb-1]);
        Print_L(p->l);
        printf(" )");
    }else{
        printf("( ");
        Print_L(p->l);
        printf(" %c ", symbols[p->syb]);
        Print_L(p->r);
        printf(" )");
    }
}

double Cal_L(double a, double b, int k)
{
    double r;
    switch (k)
    {
    case 0: r = a+b; break;
    case 1: r = a-b; break;
    case 2: r = b-a; break;
    case 3: r = a*b; break;
    case 4: r = a/b; break;
    case 5: r = b/a; break;
    default: r = 1.0; break;
    }
    return r;
}
void go(int step)
{
    if (step == 2*n-1){
        int i = 2*n-2;
        if (DblEqual_L(curr[i].val, aim)){
            i_exist++;
            if (i_save < MAX_SAVE){
                Save_L(&curr[i]);                
            }
            Print_L(&curr[i]); 
            printf("\n");
        }
        return;
    }
    int i, j, k;
    for (i = 0; i < step-1; i++)
        if (used[i])
            for (j = i+1; j < step; j++)
                if (used[j]){
                    used[i] = false;
                    used[j] = false;
                    used[step] = true;
                    curr[step].l = &curr[i];
                    curr[step].r = &curr[j];
                    curr[i].p = &curr[step];
                    curr[j].p = &curr[step];                    
                    for (k = 0;  k < 6; k++)
                    {
                        curr[step].syb = k;
                        curr[step].val = Cal_L(curr[i].val, curr[j].val, k);                        
                        go(step+1);
                    }
                    used[i] = true;
                    used[j] = true;
                    used[step] = false;
                }
}
int main( int argc, char *argv[] )
{
    int i;
    for (i = 0; i < n; i++)
    {
        curr[i].val = v[i];
        curr[i].syb = -1;
        used[i] = true;
    }
    go(n);
    return 0;
}
声明:你问我答网所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系fangmu6661024@163.com