结对项目

这个作业属于哪个课程 班级链接
这个作业要求在哪里 作业要求链接
这个作业的目标 自动生成四则运算并计算答案

Team

github链接

3119005439 曾聿昊

PSP表格

PSP Personal Software Process Stages 预估耗时(分钟) 实际耗时(分钟)
Planning 计划 30 30
· Estimate · 估计这个任务需要多少时间 500 500
Development 开发 450 490
· Analysis · 需求分析 (包括学习新技术) 120 150
· Design Spec · 生成设计文档 30 30
· Design Review · 设计复审 (和同事审核设计文档) 30 60
· Coding Standard · 代码规范 (为目前的开发制定合适的规范) 30 20
· Design · 具体设计 90 90
· Coding · 具体编码 120 120
· Code Review · 代码复审 30 20
· Test · 测试(自我测试,修改代码,提交修改) 20 20
Reporting 报告 30 30
· Test Report · 测试报告 30 30
· Size Measurement · 计算工作量 10 10
· Postmortem & Process Improvement Plan · 事后总结, 并提出过程改进计划 30 30
合计 600 640

具体实现

生成算式

一个算式由一个或多个运算符和多个运算数组成,需要生成算式,就需要考虑每个运算符左右都要有运算数。由此可以联想到二叉树结构,每个结点都可以存在最多两个子结点,我们可以类比根结点为运算符,两个子结点可以为运算符或运算数。如果此根结点的子结点也为一个运算符,则此子结点应该再生成两个对应的子结点,循环往复。直到你生成够了你想要的运算符数,则在剩余的结点都填入运算数即可生成一条正确的算式。

实现主要用Node类和My_Tree类:

class Node:
    def __init__(selfs):
        self.type = 0
        self.operator = None
        self.number = None
        self.left = None
        self.right = None
        self.op_priority = {'+': 1, '-': 1, '*': 2, '/': 2}

class My_Tree:
    def __init__(self):
        self.root = Node()
        self.op_list = ["+", "-", "*", "/"]
        self.type = [1, 2]
        self.middle_formula = list()
        self.after_formula = list()
        self.formula = list()
        self.answer = list()

建树

    def create(self, num_range, number):
        num = 0
        while num < number:
            degree = random.choice([1, 2, 3])
            empty_node = [self.root]
            for _ in range(degree):
                node = random.choice(empty_node)
                empty_node.remove(node)
                node.operator = random.choice(self.op_list)
                node.type = 2
                node.left = Node()
                node.right = Node()
                empty_node.append(node.left)
                empty_node.append(node.right)

            for node in empty_node:
                node.type = 1
                num_type = random.choice(self.type)
                if num_type == 1:
                    node.number = random.randint(1, number)
                else:
                    node.number = Fraction(random.randint(1, num_range), random.randint(1, num_range))
            try:
                self.root.get_answer()
                self.middle_formula = self.root.get_formula()
                self.after_formula = Convert.get_after_formula(self.middle_formula)
                output = Convert.std_output(self.middle_formula)
                if isinstance(self.root.number, Fraction):
                    answer = Convert.std_fraction(self.root.number)
                else:
                    answer = self.root.number
                if answer in self.answer:
                    continue
                else:
                    self.formula.append(output)
                    self.answer.append(answer)
            except NegativeError:
                continue
            except ZeroDivisionError:
                continue
            else:
                num += 1
        return self.formula, self.answer

运算优先级实现

小括号处理

小括号是用来解决运算时优先级的问题,由我们上面所述的二叉树算式生成来看,只要父母结点的运算符优先级大于等于我们的子结点的子树时,便在子树上添加小括号

    def get_formula(self):
        formula = list()
        if self.type == 1:
            return [self.number]
        elif self.type == 2:
            if self.left.type == 2 and \
                    self.op_priority[str(self.operator)] > self.op_priority[str(self.left.operator)]:
                formula.append('(')
                formula += self.left.get_formula()
                formula.append(')')
            else:
                formula += self.left.get_formula()

            formula.append(self.operator)
            if self.right.type == 2 and \
                    self.op_priority[str(self.operator)] >= self.op_priority[str(self.right.operator)]:
                formula.append('(')
                formula += self.right.get_formula()
                formula.append(')')
            else:
                formula += self.right.get_formula()
            return formula

运算结果的计算

中缀表达式和后缀表达式的区别

中缀表达式就是我们常见的式子,如1+1,运算符在运算数中间表示,而后缀表达式则是运算符在运算数的后面,如1 1 +

中缀表达式更符合我们人的理解和计算,但是对于计算机的堆栈实现来说,后缀表达式则更符合计算机的执行顺序,效率也会更高。

中缀表达式转后缀表达式

因为最后计算需要用到后缀,所以我们要先把人理解的中缀变为计算机理解的后缀,这转变过程就称为逆波兰算法

我们用一个算式例子来了解一下什么是逆波兰算法:

2+3*4+(5*6+7)*8

我们需要判断运算符的优先级,如*的优先级比+高

接着我们需要用到两个栈,第一个栈存储运算符,第二个栈存储后缀表达式的结果

中缀表达式从左到右开始读取,遇到运算数直接存入第二个栈,此时第一个栈为空,第二个栈为2。

读取++号也入栈,因为只有+一个运算符,所以优先级肯定是最高的,此时第一个栈为+,第二个栈为2

读取3,运算数直接入第二个栈,+2 3

读取*,这个*+的优先级高,所以*入栈,此时第一个栈为+ *,第二个栈为2 3

读取4,第一个栈为+ *,第二个栈为2 3 4

读取+,这个+号的优先级比目前第一个栈的栈顶*要低,所以弹出*到第二个栈中,然后第一个栈仅剩下+,与新碰到的+运算级相同,仍要弹出+,此时第一个栈为空,再把新遇到的+压入第一个栈。完成这步后,第一个栈为+,第二个栈为 2 3 4 * +

下面开始碰到左括号,左括号优先级高,不出栈,继续读入5。此时第一个栈为+ (,第二个栈为2 3 4 * + 5

读取*,因为在处理括号优先级的问题,所以先不输出左括号,直至碰到下一个右括号。此时第一个栈为+ ( *,第二个栈为 2 3 4 * + 5 6

读取+,优先级比*低,所以把*弹出,把+号压入第一个栈,再读入7,此时第一个栈为+ ( +,第二个栈为2 3 4 * + 5 6 * 7

开始碰到右括号,把栈中的括号弹出,但是左括号并不是栈顶,所以要先要把栈顶的+给弹出,左右括号不会真正输出到第二个栈,仅仅代表一种逻辑的关系。此时第一个栈为+,第二个栈为2 3 4 * + 5 6 * 7 +

继续读取*,优先级比+高,直接入第一个栈。

接着读取8,直接入第二个栈。

此时输入为空了,把第一个栈的运算符全部按顺序弹出到第二个栈作为最终的输出。所以第一个栈为空,第二个栈为2 3 4 * + 5 6 * 7 + 8 * +,第二个栈的结果就是最终计算机要计算的后缀表达式

代码如下

    def get_after_formula(formula):
        op_priority = {'(': 0, ')': 0, '+': 1, '-': 1, '*': 2, '/': 2}
        postfix_formula = list()
        op_list = list()
        for item in formula:
            if isinstance(item, int) or isinstance(item, Fraction):
                postfix_formula.append(item)
            elif item == '(':
                op_list.append(item)
            elif item == ')':
                while op_list[-1] != '(':
                    postfix_formula.append(op_list.pop())
                op_list.pop()  #
            else:
                while len(op_list) > 0 and op_priority[op_list[-1]] >= op_priority[item]:
                    postfix_formula.append(op_list.pop())
                op_list.append(item)

        while op_list:
            postfix_formula.append(op_list.pop())
        return postfix_formula
计算后缀表达式

2+3*4+(5*6+7)*8,后缀表达式为2 3 4 * + 5 6 * 7 + 8 * +

2,3,4进栈,读到*,把两个操作数3和4弹出,计算得到12压回栈,此时栈为2,12。又读到+,弹出2和12,压回相加结果为14进栈。

5,6压入后,此时栈为14,5,6。读到*,计算5*6得到30压回栈,得到的栈为14,30。读到7,压入栈,得到14,30,7。

读到+,把30和7相加得37,压回栈,得到14,37。读到8,可以直接压入栈,得到14,37,8

读到*,把37*8的结果296压入栈,得到14,296

最后读到+,把14和296相加得到最终的结果310。

class Calculator:
    def eval_expr(op_code, a, b):
        answer = 0
        if op_code == "+":
            answer = operator.add(a, b)
        elif op_code == "-":
            if operator.lt(a, b):
                raise NegativeError()
            else:
                answer = operator.sub(a, b)
        elif op_code == "*":
            answer = operator.mul(a, b)
        elif op_code == "/":
            if b == 0:
                raise ZeroDivisionError
            answer = operator.truediv(a, b)
            if isinstance(answer, float):  # if answer is float/double turn to Fraction
                answer = operator.truediv(Fraction(a), Fraction(b))
        return answer

异常处理

表达式的结果不能为负,定义一个异常类即可

class NegativeError(Exception):
    def __init__(self):
        super(NegativeError, self).__init__()

真分数的分母不能为0,对于这样的情况,直接用python的ZeroDivisionError异常类就可以。

性能分析

代码覆盖率

结对项目

准确性测试

手工计算前2题,其他直接过,在Score.txt里看到的结果与预期一致

结对项目

结对项目

结对项目

上一篇:旧版Vue配置API_ROOT,开发、生产地址切换


下一篇:Flink流处理-Task之BaseTask