[原创] c语言使用二叉树解析多项式并求值

liu583685 2020-6-11 13:53 楼主

主要实现解析多项式数据计算，如果有需求做基于单片机的简单计算器，那么是足够了。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>


typedef enum meth
{
    ADD_M = 0,  //加法
    SUB_M,      //减法
    MUL_M,      //乘法
    DIR_M,      //除法
    SIN_M,      //正弦
    COS_M,      //余弦
    TAN_M,      //正切
    VLAUE = 100      //数字
} TMeth_t;

typedef struct node
{
    double value;        //节点值
    TMeth_t method;     //节点方法
    struct node* Lchild;
    struct node* Rchild;
} Tnode_t;

const char method_D[][20] = { "+","-","*","/" };
const char method_S[][20] = { "sin(", "cos(", "tan("};


//(2*1)+(2*1)*1

double cal_tree(Tnode_t* root)
{
    switch (root->method)
    {
    case VLAUE:
        return root->value;
    case ADD_M:
        return cal_tree(root->Lchild) + cal_tree(root->Rchild);
    case SUB_M:
        return cal_tree(root->Lchild) - cal_tree(root->Rchild);
    case MUL_M:
        return cal_tree(root->Lchild) * cal_tree(root->Rchild);
    case DIR_M:
        return cal_tree(root->Lchild) / cal_tree(root->Rchild);
    case SIN_M:
        return sin(cal_tree(root->Lchild));
    case COS_M:
        return cos(cal_tree(root->Lchild));
    case TAN_M:
        return tan(cal_tree(root->Lchild));
    default:
        return 0;
        break;
    }
}

//判断字符串为纯数字
int checkNum(char* str, int len)
{
    for (int i = 0; i < len; i++)
    {
        if (str[i] == '.'){
            continue;
        }

        if (str[i] < '0' || str[i] > '9'){
            return 0;
        }
    }
    return 1;
}

//处理带括号的算法
char serchBraMethod(char* str, int len, TMeth_t* Method, char* Method_str)
{
    unsigned int i = 0, j = 0;

    for (i = 0; i < sizeof(method_S) / 20; i++) 
    {
        for (j = 0; j < strlen(method_S[i]); j++)
        {
            if (str[j] != method_S[i][j])
            {
                break;
            }
        }

        if (j == strlen(method_S[i]))
        {
            *Method = (TMeth_t)(i + 4);
            memcpy(Method_str, method_S[i], strlen(method_S[i]));

            return 1;
        }
    }

    return 0;
}


//寻找根节点方法
char* serchRootMethod(char* str, int len, TMeth_t* Method, char* Method_str)
{
    char* Method_H[sizeof(method_D) / 20] = { 0 };

    char  flag = 0;

    for (int i = 0; i < sizeof(method_D) / 20; i++) {
        for (int j = 0; j < len; j++) {
            if (str[j] == '(') {
                flag++;
            }
            if (str[j] == ')') {
                flag--;
            }

            //括号之外的方法
            if (flag == 0 && str[j] == method_D[i][0]) {
                Method_H[i] = &str[j];
                *Method = (TMeth_t)i;
                memcpy(Method_str, method_D[i], strlen(method_D[i]));
                return Method_H[i];
            }
        }
    }

    return str;
}


//构建二叉书
Tnode_t* buildTree(char* str, int len)
{
    if (str == NULL || len == 0)
        return NULL;
    Tnode_t* root = (Tnode_t*)malloc(sizeof(Tnode_t));
    char* s_ptr = NULL, * e_ptr = NULL, MethStr[20] = { 0 };
    char* str_cp = (char*)malloc(len + 1);

    if (str_cp == NULL)
        return NULL;

    memset(str_cp, 0, len + 1);
    memcpy(str_cp, str, len);
    printf("str_cp: %s\n", str_cp);

    if (checkNum(str_cp, len) || (len >= 2 && str_cp[0] == '-' && str_cp[1] != '\0' && checkNum(str_cp+1, len - 1)))
    {
        root->method = VLAUE;
        root->value = atof(str_cp);
        root->Lchild = NULL;
        root->Rchild = NULL;

        return root;
    }
    else
    {
        //寻找根方法
        s_ptr = serchRootMethod(str_cp, len, &root->method, MethStr);

        //递归方法
        if (str_cp != s_ptr)
        {
            printf("MethStr:【%s】\n", MethStr);
          
            root->Lchild = buildTree(str_cp, s_ptr - str_cp);
            root->Rchild = buildTree(s_ptr + strlen(MethStr), strlen(s_ptr) - strlen(MethStr));

            if (root->Lchild == NULL || root->Rchild == NULL)
            {
                if (root->Lchild != NULL)
                {
                    free(root->Lchild);
                }

                if (root->Rchild != NULL)
                {
                    free(root->Rchild);
                }

                free(root);
                return NULL;
            }
        }
        //去括号
        else
        {
            if (1 == serchBraMethod(str_cp, len, &root->method, MethStr))
            {
                printf("MethStr:【%s】\n", MethStr);

                root->Lchild = buildTree(str_cp + strlen(MethStr), len - 1 - strlen(MethStr));

                if (root->Lchild == NULL){
                    free(root);
                    return NULL;
                }
            }  
            else
            {
                free(root);
                root = NULL;
                if (len - 2 >= 0)
                {
                    return buildTree(str_cp + 1, len - 2);
                }   
            }
        }
    }

    free(str_cp);
    return root;
}

//替换x变量
char* replace_x(double x, char* fxrule, int rulelen)
{
    if (fxrule == NULL || rulelen == 0){
        return NULL;
    }

    char* location_X = strstr(fxrule,"x");
    if (location_X == NULL)
        return NULL;

    char replace[20] = { 0 };

    snprintf(replace, sizeof(replace), "%f", x);

    char* newRule = (char*)malloc(rulelen + strlen(replace)+20);

    memset(newRule, 0, sizeof(rulelen + strlen(replace)));

    memcpy(newRule, fxrule, location_X - fxrule);

    memcpy(newRule + (location_X - fxrule), replace, strlen(replace));

    memcpy(newRule + (location_X - fxrule) + strlen(replace), location_X + 1, strlen(replace));

    return newRule;
}



//根据变量与对应法则求值
int equation(double *fx, double X, char* fxrule, int rulelen)
{
    char* newR = fxrule, *saveR = NULL;

    if (fx == NULL || fxrule == 0){
        return -1;
    }

    do
    {
        saveR = newR;
        newR = replace_x(X, saveR, strlen(saveR));

        if (newR == NULL)
        {
            newR = saveR;
            break;
        }
        
        if (newR != NULL && saveR != fxrule)
        {
            free(saveR);
        }

    } while (newR != NULL && strstr(newR,"x"));



    printf("fxrule:%s\n", fxrule);
    printf("newRule: %s\n", newR);
   
    Tnode_t* tree = buildTree(newR, strlen(newR));

    if (newR != fxrule)
    {
        free(newR);
    }
    
    if (tree != NULL)
    {
        *fx = cal_tree(tree);

        return 0;
    }

    return -3;
}




int main()
{
    double A, B = 1.2;
    char a[200], b[200];

    while (1)
    {
        printf("请输入:\nF(x) = ");
        scanf("%s", a);
        printf("请输入X变量值:\n x = ");
        scanf("%s", b);
        B = atof(b);

        if (0 == equation(&A, B, a, strlen(a)))
        {
            printf("F(%s) = %f\n", b, A);
        }
        else
        {
            printf("输入有误!\n");
        }
    }
}

回复评论（6）

沙发 liu583685

//计算二叉树，并释放结点
double cal_tree(Tnode_t* root)
{
	double value;
	
    switch (root->method)
    {
    case VLAUE:
		value = root->value;
		fx_free(root);
		break;
    case ADD_M:
		value = cal_tree(root->Lchild) + cal_tree(root->Rchild);
		fx_free(root->Lchild);
		fx_free(root->Rchild);	
        break;
    case SUB_M:
		value = cal_tree(root->Lchild) - cal_tree(root->Rchild);
		fx_free(root->Lchild);
		fx_free(root->Rchild);	
		break;
    case MUL_M:
        value = cal_tree(root->Lchild) * cal_tree(root->Rchild);
		fx_free(root->Lchild);
		fx_free(root->Rchild);	
		break;
    case DIR_M:
        value = cal_tree(root->Lchild) / cal_tree(root->Rchild);
		fx_free(root->Lchild);
		fx_free(root->Rchild);	
		break;
    case SIN_M:
        value = sin(cal_tree(root->Lchild));
		fx_free(root);
		break;
    case COS_M:
		value = cos(cal_tree(root->Lchild));
		fx_free(root);
		break;
    case TAN_M:
		value = tan(cal_tree(root->Lchild));
		fx_free(root);
		break;
    default:
        return 0;
    }
	
	return value;
}

修复一个Bug, 内存泄漏

点赞 (1) 2020-6-12 09:10