Arithmetic expression generator based on binary tree data structure.
一个算术表达式可以由多个子表达式组成,一个子表达式运算完的结果又可以作为操作数参与另一个子表达式的运算,这样的结构让人很容易想到二叉树,而事实上通过谷歌搜索关于表达式方面的编程信息时,更多被提及的是Expression Tree
, 而Expression Tree
的经典实现就是使用二叉树(参见Wikipedia )
二叉表达式树的特点有:
利用这种特点并结合项目需求,我们可以大概将主要任务概括为
二叉表达式树及其结点的类签名如下
在构造方法中随机生成一个操作符作为根结点的数据,指定操作符的个数为下面插入操作符结点做准备,指定range
限制书中数据结点的数据范围, 然后调用初始化方法init()
;而初始化方法中主要是随机插入operatorCount
个操作符结点以及根据这些操作符结点的位置插入数据结点。
随机决定插入操作符的位置是当前处理结点的左或者右结点,通过操作符类型的随机性及操作符位置的随机性减少构造出来表达式出现重复的概率
以含有三个操作符的二叉表达式树为例,假如随机产生的操作符依次为+
、÷
、-
,则进行完当前操作后,可能出现的树形结构有:
逻辑比较简单,看注释即可
需要考虑的地方:
parent
引用获取当前处理结点的父结点,判断当前处理结点的的优先级是否低于父结点操作符的优先级,若是,在子表达式加上左右括号每个结点的遍历结果都存放到一个TraverseResult
对象中,其中包含了该结点对应的子表达式(形如1、1 + 2、(1 + 2) x 3 )及其运算结果,想获取表达式树的完整表达式,只需调用该树对象的getResult()
方法即可
假设随机产生的数字序列为7
、8
、5
、4
,则在上述构造的树形基础上插入数字后得到的完整表达式树结构及其中序遍历的结果如下图所示:
数据结点的数据类型全为分数
通过随机函数产生分子和分母,然后构造Fraction
对象,在构造中当内部属性赋值完之后调用reduce
方法进行化简;重写toString()
方法,主要用于分数的打印展示,处理带分数和整数的情况。
使用操作符枚举类定义操作符号与计算器的对应规则
具体的运算逻辑封装在Calculator
类中,只需通过Symbol
枚举类获取到当前操作符对应的计算器然后调用calculate
方法即可。
主程序入口在AppEntry类 , 主要介绍写入题目和答案及比对答案的代码
写入题目和答案 :随机产生运算符个数(最大为3个),结合指定的数据最大取值范围及题目数量构造若干表达式树,获取这些表达式树的中序遍历结果塞进集合results
, 将results
丢给writeList
函数处理写入文件逻辑
比对答案 :同时打开正确答案文件和用户提交的答案文件,逐行比对,用集合记录正误的题目标号,然后对集合中的数据进行格式输出处理,将得到的正误情况写入文件。
下面是生成10000道题目和答案, 模拟用户解答前20道题目并比对答案的例子。
文件说明:
测试用例在项目的test-result文件夹中
使用maven
插件对测试文件进行代码覆盖率统计,结果如下所示,有些地方(比如要将入口程序类实例化)并没有必要写进测试文件,所以统计达到的覆盖会比实际需要用到的样例测试低。
在i5-3230M处理器,win10 64位操作系统,12GB主存的机器上,简单统计生成10、100、1000、10000、100000道操作符数为3、操作数最大取值为100的题目并进行遍历的所用的时间
影响效能的因素:
递归
本项目中很多二叉树的操作使用了递归,而在递归的时候会进行很深层次的调用函数,所以需要调用很多函数递归(即为调用自身),需要建立许多的访问链和控制链,占用大量内存。而且调用时传递参数,申请空间,返回时恢复现场,都有时间的开销
IO读写
写入题目和答案等文件、比对答案中的文件读写操作会增加程序执行时间