1108|6

52

帖子

0

资源

一粒金砂(中级)

楼主

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

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

#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 == '.'){
            continue;
        }

        if (str < '0' || str > '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); j++)
        {
            if (str[j] != method_S[j])
            {
                break;
            }
        }

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

            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[0]) {
                Method_H = &str[j];
                *Method = (TMeth_t)i;
                memcpy(Method_str, method_D, strlen(method_D));
                return Method_H;
            }
        }
    }

    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");
        }
    }
}

 

此帖出自stm32/stm8论坛

234.png (20.76 KB, 下载次数: 0)

234.png
点赞 关注(1)

52

帖子

0

资源

一粒金砂(中级)

沙发
//计算二叉树,并释放结点
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, 内存泄漏


6

帖子

0

资源

一粒金砂(初级)

板凳
本帖最后由 redstone8415 于 2020-6-27 17:00 编辑

VS2019 编译不过!有几处有问题!

1.PNG (16.47 KB, 下载次数: 0)

1.PNG

2.PNG (32.18 KB, 下载次数: 0)

2.PNG

3.PNG (40.19 KB, 下载次数: 0)

3.PNG

点评

就是在VS2019上调试的,应该是有一些宏定义需要在工程里设置。  详情 回复 发表于 2020-6-27 21:08

52

帖子

0

资源

一粒金砂(中级)

4
redstone8415 发表于 2020-6-27 16:57 VS2019 编译不过!有几处有问题!

就是在VS2019上调试的,应该是有一些宏定义需要在工程里设置。


52

帖子

0

资源

一粒金砂(中级)

5
liu583685 发表于 2020-6-27 21:08 就是在VS2019上调试的,应该是有一些宏定义需要在工程里设置。

链接:https://pan.baidu.com/s/1maAioGy6thx-qGSZL8hIwg 
提取码:wq71

这个是我的源工程,你可以看看。

代码里还有内存泄露,我在arm平台上修复了,这里的代码没有改。要注意一下。


6

帖子

0

资源

一粒金砂(初级)

6

幸运时时彩平台好像还是有问题!

4.PNG (52.69 KB, 下载次数: 0)

4.PNG

6

帖子

0

资源

一粒金砂(初级)

7
本帖最后由 redstone8415 于 2020-6-30 16:21 编辑

我搞错了!没事! OK!谢谢!


您需要登录后才可以回帖 登录 | 注册

关闭
站长推荐上一条 1/9 下一条

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版

站点相关: 安防电子 汽车电子 手机便携 工业控制 家用电子 医疗电子 测试测量 网络通信 物联网

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2020 sonata9.com, Inc. All rights reserved
快速回复 返回顶部 返回列表
湖北快3代理 福建快3开奖 幸运时时彩官网 彩票高賠率好平台 一分时时彩官网 亿信彩票网址 全民彩票 福建快3走势 幸运时时彩 吉林快3开奖