四则运算
一、.题目要求
题目链接：http://www.cnblogs.com/HQL0301/p/7502315.html
二、.实现过程
项目文件结构：
1.题目的随机生成思路：
写了两种，一种类似编译原理语法树自下而上根据操作符数量递归生成，一种是自上而下根据操作数数量递归生成，两者使用python的列表来实现。因为为了实现括号随机生成，最终使用第二种方式实现。
递归思路：
每次根据countOperatorNumber，比如一开始是3个操作数，则模拟而二叉树：
如图，[[3],"+",["(",8,"+",9,")"]]为最终的递归结果，其中括号是当countOperatorNumber=2，即在返回递归列表组[8,"+",9]时候手动添加的，该效果直接取代了再随机插入括号的繁琐步骤，以下为生成表达式结果图：
def createExercises(countOperatorNumber, listExercise): # 递归随机生成四则运算表达式
其中，题目中随机生成分数的实现是根据flag=random.randint(0, 1)，为0的则调用getFraction()方法插入一个随机分数，
2.表达式结果计算：
def calculate(self, expression): # 主计算函数
用python的list模拟Java的Stack函数写了个Stack类，使用dict模拟了一个switch(因为python里没有switch)。根据生成的中缀表达式直接使用栈来实现结果计算。因为python是弱语言没有类型限制，所以列表存任何类型数据都能直接存，比较方便。
还有计算思路是每次进行两个操作数计算的时候，都直接转化成分数去计算，因此写了个Fraction类，主要方法有：
def __init__(self, numerator, denominator): def plus(self, fraction): def minus(self,fraction): def multiply(self,fraction): def divide(self,fraction): def getResult(self):
计算结果演示如下：
3.查重思路：
将中缀表达式转成后缀表达式，然后存二叉树，在使用后序遍历打印出结果进行判重比较。因为算法不强，网上又没现成的，所以只能根据百度百科思路自己编写：
将中缀表达式转换为后缀表达式的算法思想：
1.开始扫描；
2.数字时，加入后缀表达式；
3.运算符：
a. 若为 '('，入栈；
b. 若为 ')'，则依次把栈中的的运算符加入后缀表达式中，直到出现'('，从栈中删除'(' ；
c. 若为 除括号外的其他运算符， 当其优先级高于除'('以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。
4.当扫描的中缀表达式结束时，栈中的的所有运算符出栈；
存二叉树思路：
1.当左右子树均为操作数时，值大的作为左子树，另一个作为右子树； 2.当左右子树均为二叉树的时候，取它们的根节点，因为他们的根节点均为操作符，比较它们优先级，值大的整颗操作数作为新节点的左子树，另一个作为右子树； 3.当左右子树分别为二叉树和操作数的时候，二叉树作为新节点的左子树，操作数作为右子树。
查重结果演示：
总结：出了点状况，断断续续撸了几天，有些代码直接从Java版翻译过来。难点在于分数的穿插处理比较啰嗦，各个模块都得独立考虑。
不足在于算法方面比较弱，有些逻辑可能比较乱，在转后缀那块被整了好久。