数据结构实践——用二叉树求解代数表达式

本文是针对数据结构基础系列(6):树和二叉树的配套实践。

【项目 - 用二叉树求解代数表达式】
  用二叉树来表示代数表达式,树的每一个分支节点代表一个运算符,每一个叶子节点代表一个运算数(为简化,只支持二目运算的+、-、*、/,不加括号,运算数也只是一位的数字字符。本项目只考虑输入合乎以上规则的情况)。请设计算法,(1)根据形如“1+2∗3−4/5 ”的字符串代表的表达式,构造出对应的二叉树(如图),用后序遍历的思路计算表达式的值时,能体现出先乘除后加减的规则;(2)对构造出的二叉树,计算出表达式的值。

[参考解答] 程序中的btree.h,见二叉树算法库

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include "btree.h"

//用s[i]到s[j]之间的字符串,构造二叉树的表示形式
BTNode *CRTree(char s[],int i,int j)
{
    BTNode *p;
    int k,plus=0,posi;
    if (i==j)    //i和j相同,意味着只有一个字符,构造的是一个叶子节点
    {
        p=(BTNode *)malloc(sizeof(BTNode));   //分配存储空间
        p->data=s[i];                         //值为s[i]
        p->lchild=NULL;
        p->rchild=NULL;
        return p;
    }
    //以下为i!=j的情况
    for (k=i; k<=j; k++)
        if (s[k]=='+' || s[k]=='-')
        {
            plus++;
            posi=k;              //最后一个+或-的位置
        }
    if (plus==0)                 //没有+或-的情况(因为若有+、-,前面必会执行plus++)
        for (k=i; k<=j; k++)
            if (s[k]=='*' || s[k]=='/')
            {
                plus++;
                posi=k;
            }
    //以上的处理考虑了优先将+、-放到二叉树较高的层次上
    //由于将来计算时,运用的是后序遍历的思路
    //处于较低层的乘除会优先运算
    //从而体现了“先乘除后加减”的运算法则
    //创建一个分支节点,用检测到的运算符作为节点值
    if (plus!=0)
    {
        p=(BTNode *)malloc(sizeof(BTNode));
        p->data=s[posi];                //节点值是s[posi]
        p->lchild=CRTree(s,i,posi-1);   //左子树由s[i]至s[posi-1]构成
        p->rchild=CRTree(s,posi+1,j);   //右子树由s[poso+1]到s[j]构成
        return p;
    }
    else       //若没有任何运算符,返回NULL
        return NULL;
}

double Comp(BTNode *b)
{
    double v1,v2;
    if (b==NULL)
        return 0;
    if (b->lchild==NULL && b->rchild==NULL)  //叶子节点,应该是一个数字字符(本项目未考虑非法表达式)
        return b->data-'0';    //叶子节点直接返回节点值,结点中保存的数字用的是字符形式,所以要-'0'
    v1=Comp(b->lchild); //先计算左子树
    v2=Comp(b->rchild); //再计算右子树
    switch(b->data)     //将左、右子树运算的结果再进行运算,运用的是后序遍历的思路
    {
    case '+':
        return v1+v2;
    case '-':
        return v1-v2;
    case '*':
        return v1*v2;
    case '/':
        if (v2!=0)
            return v1/v2;
        else
            abort();
    }
}

int main()
{
    BTNode *b;
    char s[MaxSize]="1+2*3-4/5";
    printf("代数表达式%s\n",s);
    b=CRTree(s,0,strlen(s)-1);
    printf("对应二叉树:");
    DispBTNode(b);
    printf("\n表达式的值:%g\n",Comp(b));
    DestroyBTNode(b);
    return 0;
}

时间: 2024-11-01 11:04:34

数据结构实践——用二叉树求解代数表达式的相关文章

数据结构实践项目——树和二叉树(2)

本文针对数据结构基础系列(6):树和二叉树第7, 11-15课时 7 二叉树与树.森林之间的转换 11 二叉树遍历非递归算法 12 层次遍历算法 13 二叉树的构造 14 线索二叉树 15 哈夫曼树 [项目1 - 二叉树算法验证] 运行并重复测试教学内容中涉及的算法.改变测试数据进行重复测试的意义在于,可以从更多角度体会算法,以达到逐渐掌握算法的程度.使用你的测试数据,并展示测试结果,观察运行结果,以此来领会算法. (1)层次遍历算法的验证 [参考链接] (2)二叉树构造算法的验证 [参考链接]

遍历-数据结构问题。二叉树,程序写了编译没错,但没办法运行。求大神看下。

问题描述 数据结构问题.二叉树,程序写了编译没错,但没办法运行.求大神看下. #include #define MAXLEN 100 using namespace std; typedef char elementType; typedef struct lBnode {elementType data; struct lBnode *lchild,*rchild; }Binode,*Bitree; void create(Bitree &T) //创建二叉链表 {char ch; cin>

【算法与数据结构】查找二叉树的实现

(转载请注明出处:http://blog.csdn.net/buptgshengod) 1.题目介绍     二叉树是一种基本的数据结构.查找二叉树是一种方便与查找,删除,插入等功能的二叉树,它要求每个父节点的左分支小于父节点,右分支大于父节点.下面我们来实现下面这个查找二叉树. 2.java代码实现 public class BinaryTree { private Node root; public BinaryTree(){ root=null; } /* * 定义内部节点 */ publ

数据结构实践项目——树和二叉树(1)

本文针对[数据结构基础系列(6):树和二叉树]第1-6, 8-10课时 1 树结构导学 2 树的基本概念 3 树的基本术语 4 树的性质 5 树的存储结构 6 二叉树概念和性质 8 二叉树的存储结构 9 二叉树的基本运算及其实现 10 二叉树的遍历 [项目1 - 二叉树算法库] 定义二叉树的链式存储结构,实现其基本运算,并完成测试. 要求: 1.头文件btree.h中定义数据结构并声明用于完成基本运算的函数.对应基本运算的函数包括: void CreateBTNode(BTNode *&b,ch

数据结构实践项目——图的基本运算及遍历操作

本文是针对[数据结构基础系列(7):图]中第1-9课时的实践项目. 0701 图结构导学 0702 图的定义 0703 图的基本术语 0704 图的邻接矩阵存储结构及算法 0705 图的邻接表存储结构及算法 0706 图的遍历 0707 非连通图的遍历 0708 DFS的应用 0709 BFS的应用 [项目1 - 图基本算法库] 定义图的邻接矩阵和邻接表存储结构,实现其基本运算,并完成测试. 要求: 1.头文件graph.h中定义相关的数据结构并声明用于完成基本运算的函数.对应基本运算的函数包括

数据结构实践项目——查找(一)

本文是[数据结构基础系列(8):查找]课程的第一组实践项目. 本文针对: 0801 查找问题导学 0802 线性表的顺序查找 0803 线性表的折半查找 0804 索引存储结构 0805 分块查找 0806 二叉排序树 0807 二叉排序树(续) 0808 平衡二叉树 纸上谈兵:"知原理"检验题目 [参考(部分)] [参考(1)] 1.对于A[0..10]有序表{12,18,24,35,47,50,62,83,90,115,134} (1)用二分查找法查找 90时,需进行多少次查找可确

数据结构实践——稀疏矩阵相加

本文针对数据结构基础系列网络课程(5):数组与广义表的实践项目. [项目 - 稀疏矩阵相加] 采用三元组存储稀疏矩阵,设计两个稀疏矩阵相加的运算算法 提示1:两个行数.列数相同的矩阵可以相加 提示2:充分利用已经建立好的算法库解决问题 [参考解答1](程序中使用的头文件"tup.h"见稀疏矩阵的三元组表示算法库) #include <stdio.h> #include "tup.h" bool MatAdd(TSMatrix a,TSMatrix b,T

数据结构实践——是否二叉排序树?

本文是[数据结构基础系列(8):查找]的实践项目参考. [项目 - 是否二叉排序树?] 设计一个算法,判断给定的二叉树是否是二叉排序树. [参考解答] int JudgeBST()是设计的算法对应的实现. #include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef int KeyType; //定义关键字类型 typedef char InfoType; typedef struct node //记录类型

数据结构 实践项目——数据结构、算法、程序设计

[项目1 - C/C++语言中函数参数传递的三种方式] C语言提供了两种函数参数传递的方式:传值和传地址.在C++中,又拓展了引用方式.通过本项目,确认自己已经掌握了这三种方式的原理,为后续学习做好准备. 下面是希望能够交换两个整型变量的swap函数的三个版本(从课程主页中可以找到项目链接,复制后就能调试,不必费事敲代码): //(1)传值 void myswap(int x, int y) { int t; t=x; x=y; y=t; } //(2)传地址 void myswap(int *