面向对象第一次作业

面向对象第一次作业总结

多项式求导问题描述

定义多项式

首先是一些基本概念的声明：

**带符号整数 **支持前导 0 的带符号整数，符号可忽略，如：+02、-16、19260817 等。
因子
- 变量因子
  - 幂函数
    - 一般形式 由自变量x和指数组成，指数为一个带符号整数，如：x ^ +2。且，指数绝对值一律不得超过$ {10}^4 $。
    - 省略形式 当指数为1的时候，可以采用省略形式，如：x。
  - 三角函数 sin(x)，cos(x)，另外，本指导书范围内所有的词语“三角函数”，除非特殊说明，否则一律包含且仅包含上述两个函数）
    - 一般形式 类似于幂函数，由sin(x)，cos(x) 和指数组成，指数为一个带符号整数，如：sin(x) ^ +2。同样的，指数绝对值一律不得超过({10}^{4})。
    - 省略形式 当指数为1的时候，可以采用省略形式，省略指数部分，如：sin(x)。
- 常数因子 包含一个带符号整数，如：233。
- 表达式因子 将在表达式的相关设定中进行详细介绍。不过，表达式因子不支持幂运算。
- 嵌套因子 本次作业将支持因子嵌套在三角函数因子里面，即一个因子作为另一个三角函数因子的自变量，例如sin(x^2)，cos(sin(x)) 以及 sin(sin(cos(cos(x^2))))^2 等。但是不允许出现指数为变量的情况，指数依然只能是带符号整数，例如sin(x) ^ sin(x)是不合法的，因为指数不是自变量。也不允许幂函数的自变量为除了x之外的因子，例如1926^0817是不合法的，因为幂函数的自变量只能为x。
项
- 一般形式由乘法运算符连接若干任意因子组成，如：x * cos(x) * x，sin(x ^ 2) * cos(sin(x)) ^ 2 * x ^ -2 等。
  - 项内因子不仅仅是同类因子
- 特殊形式
  - 第一个因子为常数因子 1 且其后跟着乘号的时候，可以省略该常数因子或表示为正号开头的形式，如：x ^ 2 * x ^ -1、 + x ^ 2、+ cos(x) * cos(x)、 sin(x) * cos(x)。
  - 第一个因子为常数因子 -1 且其后跟着乘号的时候，可以表示为负号开头的形式，如：-x ^ 2、- cos(x) * sin(x)。
表达式 由加法和减法运算符等若干项组成，如： (-1 + x ^ 233)* sin(x^2) ^ 06 - cos(sin(x)) * 3 * sin((x))。此外，在第一项之前，可以带一个正号或者负号，如：- -1 + x ^ 233、+ -2 + x ^ 1926。此处有几点注意：
- 表达式因子，表达式可以作为因子，其定义为被一对小括号包裹起来的表达式，即我们允许诸如(x * cos(x)) 这种式子的出现
- 空串不属于合法的表达式
空白字符 在本次作业中，空白字符包含且仅包含<space>和。其他的除了上述会用到的字符之外，均属于非法字符。

问题

输入一个多项式，对其求导，并且使用以上的格式对于求导后的表达式进行输出

程序结构与问题建模方法

作业1

第一次作业我设计了三个类， Item, stringparse和Polynominal

Item

Item类主要用来存储表达式中的每一项

boolean positive存储这是正项还是负项

coef存储了系数

exponent存储了x的几次幂

Public void calculateDerivate()用来对项求导，为mutable方法
StringParser

String parser读入一个字符串作为要parse的String

根据问题中因子，项，表达式的hierarchical的定义，分别返回不同类型。
主要有以下功能
1. parseOperator
2. parseInteger
3. parseExponent
4. parseItem
Polynominal

用来存储多项式的类

主要有以下两个方法
1. readPolyFromString 方法读取多项式
2. calcDerivate用来求导

作业2

作业2我的设计基本和作业1相同

Item

加入了sinExp，代表sin(x)的sinExp次方

加入了cosExp，代表cos(x)的cosExp次方
StringParser

加入了parseTrianFunc

作业3

对于上述的表达式求值，第三次作业中我的类设计如下

主要有四个类

String Parser

String parser读入一个字符串作为要parse的String

根据问题中因子，项，表达式的hierarchical的定义，分别返回不同类型。
对于任何因子，项，最底层的parse需要完成以下几件事情
1. 跳过空格 skipSpace()
2. 是否string的结尾 isEnd()
3. 读取一个符号 parseOperator()
4. 读取一个数字 parseInteger()
5. 读取 sin, cos readTrianFuncAndSkip()
6. 读取一个x
7. 识别并且跳过^
在完成以上5件事情，考虑边界条件把以上功能做的足够robust后，接下来就可以按照因子，项和表达式，以及子表达式， sin， cos表达式的读取了。
对于基本的因子
1. parseInteger读取常数因子
2. parseTrianFunc读取三角函数因子
3. parseExponent读取指数因子
读取三角函数的代码实例如下：
```
public TriFunc parseTrianFunc() throws NumberFormatException {
    if (isNextTrianFunc()) {
        int curType = readTriaFuncAndSkip();
        BigInteger curExp;
        skipSpace();
        if (!isEnd() && getCurChar() == '^') {
            movePointer();
            try {
                curExp = parseInteger();
            }
            catch (NumberFormatException e) {
                throw e;
            }
            if (curExp.abs().compareTo(new BigInteger("10000")) == 1) {
                throw new NumberFormatException();
            }
            return new TriFunc(curType, curExp);
        }
        else {
            curExp = new BigInteger("1");
            return new TriFunc(curType, curExp);
        }
    }
    else {
        throw new NumberFormatException();
    }
}
```
在完成了基本因子的读取后，通过基本函数的组合来实现复杂项和表达式的读取
1. parseItem（）函数读取一个项
2. ParseExpression() 函数读取一个表达式
3. parseNestedExpression() 读取一个带有sin, cost嵌套表达式
简而言之，表达式由项组成， nestedExpression, 由（表达式）或者Sin(表达式）或者cos(表达式组成)

任何一次parse都是以上几种parse按照规则的组合

Item

Item类是用来存储项的数据结构，一个项包含了sin, cost, exponent, coef和子表达式list

这个类中的derivate对该项进行求导，返回一个含有很多项的list

public LinkedList<Item> calcDerivative() {
    LinkedList<Item> result = new LinkedList<Item>();
    if (!exponent.equals(new BigInteger("0"))) {
        Item tmpItem = new Item(positive, coef.multiply(exponent),
                exponent.subtract(new BigInteger("1")),
                sinExp, cosExp, exprList);
        if (!tmpItem.coef.equals(new BigInteger("0"))) {
            result.addLast(tmpItem);
        }
    }
    if (!sinExp.equals(new BigInteger("0"))) {
        Item tmpItem = new Item(positive, coef.multiply(sinExp),
                exponent, sinExp.subtract(new BigInteger("1")),
                cosExp.add(new BigInteger("1")), exprList);
        if (!tmpItem.coef.equals(new BigInteger("0"))) {
            result.addLast(tmpItem);
        }
    }
    if (!cosExp.equals(new BigInteger("0"))) {
        Item tmpItem = new Item(!positive, coef.multiply(cosExp),
                exponent, sinExp.add(new BigInteger("1")),
                cosExp.subtract(new BigInteger("1")), exprList);
        if (!tmpItem.coef.equals(new BigInteger("0"))) {
            result.addLast(tmpItem);
        }
    }
    // calc nested expr
    for (int i = 0; i < exprList.size(); i++) {
        DerivativeReturn derResult = exprList.get(i).calcDerivate();
        LinkedList<NestedExpression> nestList =
                new LinkedList<NestedExpression>();
        for (int j = 0; j < exprList.size(); j++) {
            if (j != i) {
                nestList.addLast(exprList.get(j));
            }
        }
        for (int j = 0; j < derResult.getNestedExpressionList()
                                    .size(); j++) {
            nestList.addLast(derResult.getNestedExpressionList().get(j));
        }
        Item tmpItem = new Item(positive,
                coef.multiply(derResult.getCoef()),
                exponent, sinExp, cosExp, nestList);
        if (!tmpItem.coef.equals(new BigInteger("0"))) {
            result.addLast(tmpItem);
        }
    }
    return result;
}

Expression

这个类包含了表达式所需要的所有操作。

表达式是由很多项的由加法减法构成的组合，对表达式求导等同于对于每一项进行递归求导
NestedExpression

NestedExpression类是expression类的扩展，包含了sin(expression), cos(expressio)和（expression）

用于处理带有sin, cos和（）的表达式

工程的UML图

度量分析

作业1

第一次作业的复杂度整体较好

作业2

作业二中parseItem的复杂度较高, Cyclomatic complexity控制的不好，条件判断的结构设计不好，需要改进。

作业3

parseItem和ParseNestedExpression在设计复杂度控制的不够好，代码comment ratio有些低，不利于之后的维护，这些在以后的作业中需要改进。

bug 分析

三次作业没有被发现bug， 发现别人bug3处，通过看指导书中的定义，找一个空格判断之类的盲区，对其他人的代码进行测试。

代码重构

三次作业基本架构不需要重构，如果要提升的话，方法如下：

String parse和Item类写的有些累赘，其中Item还可以拆成TrainFunction, Exponent, Factor, SingleInteger四个类，分别进行parse和合并，这样有助于提升代码的可读性以及后期敏捷开发。![]