BUAA-OO-Lab1-Java面向对象

一、面向对象程序设计

1.1 面向对象程序设计

面向对象程序设计（Object-Oriented Programming）是一种基于对象的编程范式。相对面向过程程序设计（Procedure-Oriented Programming）而言，OOP 不 ”注重“ 代码实现细节，而更强调对象所具备的功能。从这个角度来看，OOP 要更为抽象，它将程序设计的重点放在了对象与对象的交互上，将对象内部的功能实现（POP）隐藏起来。

1.2 类和对象

类（Class）：类是描述一类对象的状态（data：attributes）和行为（code：methods）的模板。

对象（Object）：对象是某一个类的实例。

众所周知，万物皆对象，那么就拿手边的书举个简单例子。现在有一个 Book 类，它长这样：

 public class Book{
     private final int pages;
     private final String bookName;
     private final String writer;
     public Book(int pages, String bookName, String writer){
         this.pages = pages;
         this.bookName = bookName;
         this.writer = writer;
     }
     public int getPages(){ return this.pages; }
     public abstract String getBookName(){ return this.bookName; }
     public abstract String getWriter(){ return this.writer; }
 }

其中，页码数（pages）、书名（bookName）和作者（writer）就是 Book 类的 attributes，而获取页码数、书名与作者名便是 Book 类所支持的 methods。

现在，我们用构造器（constructor）实例化一本书 book：

 Book book = new Book(10, "OOP-Java", "Zry");

然后我们就得到了一本由 Zry 写的10页的名为 OOP-Java 的书了。

接下来，我们就可以使用这本书所支持的方法了：

 int pages = book.getPages();            //pages = 10
 String bookName = book.getBookName();   //bookName = "OOP-Java"
 String writer = book.getWriter();       //writer = "Zry"

1.3 继承与接口

继承（Inheritance）：子类继承父类的特征和行为，使得子类具有父类的实例域和方法。

几乎所有面向对象程序设计语言都支持继承，它提高了代码的复用性，即子类不用再去父类已实现的特征与行为，那么，上面的例子就可以变成：

 public class ProgramBook extends Book{
     private String language;
     public ProgramBook(int pages, String bookName, String writer, String language){
         super(pages, bookName, writer, language);
         this.language = language;
     }
     public String getLanguage(){ return this.language; }
 }

ProgramBook 类较 Book 类增加了编程语言（language）这一属性以及对应的 getLanguage 这一方法。构造方式变为：

 ProgramBook programBook = new ProgramBook(10, "OOP-Java", "Zry", "Java");

接口（Interface）：是一系列抽象方法的集合，可以被类实现。

Java 不支持多继承（C++支持多继承），但 Java 可以用 多个接口辅以单继承来达到类似多继承的效果。一旦我们知道类 A 实现了接口 B，那么便可以直接对类 A 的实例（对象）调用接口 B 中的方法。此外，我们还可以用接口来引用实现了它的对象（但不能实例化一个接口，接口没有构造器！）。

二、问题重述

至此，你已经完全掌握面向对象程序设计的基本内容了！我们来试试吧！

2.1 多项式化简 & BNF 表述

（以下问题描述中，下划线为新增需求模拟）

输入：一行字符串形式的关于自变量 x 的多项式。

至多三个自定义函数。

输出：展开多项式中所有不必要括号。

BNF 表述：

• 表达式 \rightarrow [加减] 项 | 表达式 加减 项

• 项 \rightarrow [加减] 因子 | 项 * 因子

• 因子 \rightarrow 变量因子 | 常数因子 | 表达式因子

• 变量因子 \rightarrow 幂函数 | 自定义函数调用 | 三角函数 | 求和函数

• 常数因子 \rightarrow 带符号整数

• 表达式因子 \rightarrow '(' 表达式 ')' [指数]

• 幂函数 \rightarrow 'x' [指数]

• 指数 \rightarrow '**' ['+'] 允许前导零的整数

• 带符号整数 \rightarrow [加减] 允许前导零的整数

• 允许前导零的整数 \rightarrow (0|1|2|…|9){0|1|2|…|9}

• 加减 \rightarrow '+' | '-'

• 三角函数 \rightarrow 'sin' '(' 因子 ')' [指数] | 'cos' '(' 因子 ')' [指数]

• 自定义函数定义 \rightarrow 自定义函数名 '(' 函数自变量 [',' 函数自变量 [',' 函数自变量 ]] ')' '=' 函数表达式

• 函数自变量 \rightarrow 'x' | 'y' | 'z'

• 自定义函数调用 \rightarrow 自定义函数名 '(' 因子 [',' 因子 [',' 因子 ]] ')'

• 自定义函数名 \rightarrow 'f' | 'g' | 'h'

• 求和函数 \rightarrow 'sum' '(' 'i' ',' 常数因子 ',' 常数因子 ',' 求和表达式 ')'

• 函数表达式 \rightarrow 表达式

• 求和表达式 \rightarrow 因子

其中

• {} 表示允许存在 0 个、1 个或多个。

• [] 表示允许存在 0 个或 1 个。

• () 内的运算拥有更高优先级，类似数学中的括号。

• | 表示在多个之中选择一个。

• 上述表述中使用单引号包裹的串表示字符串字面量，如 '(' 表示字符 (。

函数形式说明：

• 自定义函数

  • 自定义函数的定义形如 f(x, y, z) = 函数表达式 ，比如 f(y) = y**2，g(x, y) = sin(x)*cos(y)，h(x, y, z) = x + y + z 。

  • f 、g、h 是函数的函数名，函数名只使用 f ，g，h，且不出现同名函数的重复定义。

  • x、y、z 为函数的形参，形参个数为 1~3 个。

  • 函数表达式为一个关于形参的表达式。函数表达式的一般形式参见形式化定义。

  • 自定义函数的调用形如 f(因子, 因子, 因子) ，因子 为函数调用时的实参。

  • 函数调用的结果中应只包含自变量 x。

• 求和函数

  • 求和函数的一般形式为 sum(i, s, e, t)，其含义为 \sum_{i=s}^et。

  • 循环变量只能是字符 i 。

  • s 与 e 为求和的下限和上限，二者都是常数因子。在循环时，循环变量 i 的初值为 s，每次迭代 i 自增 1 并计算表达式的值，当 i 大于 e 时停止计算，并将计算结果求和。（若初始 s > e，则该函数结果为 0）。

  • 求和表达式 t 是一个因子，其中可以包含循环变量 i 。

输入输出示例：

 Basic version
 Input:
 (3*x+1)**+2+x**2*-9
 Output:
 6*x+1
 ​
 Enhanced verison
 Input:
 3
 f(y,x,z)=(x)**2+y*z
 g(y,z)=y**2*z
 h(x)=x**0
 f(g(sin(x),cos(sin(x))),sum(i,1,2,sin(i)),f(2,4,1))+sum(i,2,1,0)*h(0)
 Output:
 sin(1)**2+sin(2)**2+18*sin(x)**2*cos(sin(x))+2*sin(1)*sin(2)

2.2 需求分析 & 设计思路

拿到基础问题描述后，第一想法自然是：这题我熟！写了一年半的 C 换成 Java 不还是一样写吗？逆波兰表达式、表达式树、分治之类的做法一股脑全涌了上来。但仔细一想，之前做过的表达式解析都是数值计算， ” 维护 “ 计算结果（这里隐藏的问题是同类项合并，所有数值计算结果均为数字，即同一类）。但这里涉及到未知数 x 就意味着更多的数据类型，意味着要为每一种数据类型 ” 维护 “ 一个计算结果， 意味着每种数据类型都是一个类。

繁琐的数据类型，终归不如大一统理论看着心情舒畅。于是乎， Base 类应运而生。只要将所有数据类型的数据形式囊括进 Base 类，就能抓住主线，将问题 ” 化繁为简 “ ！

对于基础需求来说，Base 类的数据域如下：

 public class Base{
     private int coefficient;
     private int index;
     // data format:coefficient * x ** index
 }

这样一来，就初步形成了 Expression -> Base 的数据形式。

表达式类 Expression 的数据类如下：

 public class Expression{
     private ArrayList<Base> bases;
 }

数据结构层次如下：

三、求解 & 迭代开发

3.1 试错：面向过程

较 C 而言，Java 有正则表达式这一强大的工具，这就为我的面向过程程序设计提供了一大助力。

首先，用正则表达式处理括号：

1. 识别表达式因子：表达式因子 \rightarrow '(' 表达式 ')' [指数]，按其指数展开为若干'(' 表达式 ')' * '(' 表达式 ')' 的形式。

2. 识别内层括号：获取最底层的无括号表达式，自底向上逐级递归处理。

至此，括号问题被解决了，问题被简化成了仅含 + 、 - 、 * 与 ** 运算符的表达式化简问题，无论是按 * 与 + -进行分治还是中缀转后缀表达式再求解，整个问题都被转变为了字符串处理——一个面向过程程序设计问题。

然而，这是一个庞大的字符串处理问题。为了处理括号，我在 Coding 中使用了大量（超过十个）长正则表达式进行模式匹配。为了处理各种数据类型，我又使用了数十个诸如 replace 的小 tricks 来简化步骤。这样一来，各式各样的 Bug 层出不穷，因为一旦场景枚举出现了考虑不周的情况，便会引起一系列相应问题。

此外，在面对需求可能会灵活变动的问题时，采用这种对问题针对性极强的设计方案是非常不明智的。

3.2 重构：面向对象

喜闻乐见，在问题新增了三角函数、自定义函数与求和函数后，我便开始了重构之旅。

同时看着自己基础版的代码和新增需求，其实硬要写，依旧可以继续面向过程一路到底，只是需要分类讨论的情况数会随着需求的线性增加而成指数级变化，这意味着可能要修改 / 加入数十个长正则表达式，也意味着无穷无尽的 Bug 。

痛定思痛，与其在面向过程的道路上一错到底，不如推倒重来，加入 递归下降 的队伍，按照 BNF 表述按部就班地建立对应的类，逐步进行解析。这样一来，重建好文法、词法分析的框架后，增加新需求便只要增加、修改新数据类型对应的类以及 Base 类对应的新增的运算法则与存储逻辑就 OK 了。

四、浅析程序结构

4.1 从类图看整体框架

从所有类的整体关系来看，所有数据类（Number：整数；Power：幂函数；Sum：求和函数；TriFunc：三角函数；SelfFunc：自定义函数）均实现了 Factor 接口。因此，在递归下降对表达式进行解析时，可以使用工厂模式来进行类的创建。此外，在 Term、Base 和 Expr 三个类构成的三角关系中，Term 与 Expr 分别为形式化表述中的项与表达式，而 Base 为项 Term 的化简版（合并 Term 中因子后的结果，为统一存储的数据形式）。

因此，在拿到输入 Input 后，FuncTable 类将对自定义函数进行解析，Scan -> Expand 将对输入表达式进行预解析（主要为处理连续正负号与部分指数的展开）。然后，将形式规范的解析结果送入 Lexer 与 Parser 进行解析，获得表达式的内部结构。

部分关键类的内部定义如上图。其中，Base 类中定义了对各类因子的加减乘的运算与合并法则；Parser 类中的 peekToFactor 方法使用工厂模式创建数据类；Expr 类中的 combineBases 方法与 Term 类中的 sortFactors 方法则关联了 Expr、Term 和 Base 三者，将解析与化简进行串联。

4.2 从 OO 度量看内聚与耦合

OCavg：平均操作复杂度。

OMax：最大操作复杂度。

WMC：加权操作复杂度。

这里看出所有 数据类 的基本复杂度（如 Power、Number、TriFunc等）均较低，而在 Sum、SelfFunc 等类中，因为在个人设计中仍然使用了一定量的字符串替换（写起来简单粗暴），所以操作复杂度平均高了一到两个操作数。而 Expand 和 Scan 这样用于对字符串进行预处理的类（基于来自基础需求的设计经验，还是使用了大量的字符串替换及部分正则表达式），虽然可以保证正确性，但确实会增加固定的操作次数。最后，内含各种数据类型合并、计算功能的 Base 类的加权操作复杂度较高，考虑到其运算功能本身的复杂性，所以也是可以接受的。

在整体设计过程中，因为以数据为主线，所以各个负责解析的类之间存在表达式数据的数据耦合，各个数据类之间无耦合关系，数据结构类与数据类之间存在数据耦合。总的来说，除了数据耦合，各类之间不存在其他耦合关系，而是将自己负责的功能完全内聚在类内部，真是神奇的面向对象。

五、测试 & Bug 分析

5.1 功能测试

写完代码第一件事，自然是用最 ” 简单 “ 的测试数据来检查代码是否能跑通基本流程，手动构造一些测试数据来确保所有数据类型都能被正确解析、合并。然后，就可以着手构造一些边界条件附近的测试数据，并随机生成测试数据 + 自动化评测来 ” 轰炸 “ 代码了，随机数据测个几千上万条就差不多了。

5.2 从复杂度看 Bug 高发路段

CogC：认知复杂度。

ev(G)：基本圈复杂度。

iv(G)：设计复杂度。

v(G)：圈复杂度。

首先，节选几个复杂度最高的方法。（Average 和 Total 表项均计算整个项目中的所有方法）

其中，

Expand 类中的 findIndex 和 indexExpand 方法负责表达式因子的指数展开，Scan 类中的 triFuncScan 方法负责三角函数的括号匹配，这些方法均使用了面向过程程序设计方法进行字符串处理；

Expr 类中的 combineBases -> Term 类中的 sortFactors -> Base 类中的 baseEqual 和 toString ，是一揽子同类项合并方案，考虑到本项目对算法的低需求（能跑就行，不 care 时间），我在设计时也就一切从简——使用暴力搜索匹配的方式进行化简，因而复杂度较高。

最后是 Base 类中的 addFactor 方法，它本质上是 Parser 中 peekToFactor 方法的延拓，是工厂模式的具体实现部分。为了使用 Base 类对所有数据进行统一处理，我认为这部分复杂度的牺牲是值得的。

找到了抬高复杂度的 “ 祸害 ”，它们又会产生什么样的 Bug 呢？

其实，后两类方法虽然复杂度较高，但其实逻辑清晰，换句话说，它们复杂得情有可原，其实并不容易出 Bug （实际测试过程中也确实如此）。问题主要集中在第一部分——字符串处理。

到头来，还是面向过程的锅。正则 + replace 真是简单，“有效” 而又粗暴，例如直接删去 “1*” 、将 " sin(- "替换为 " -sin( " 、将 " -1" 替换为 " -1*1"，诸如此类的取巧其实可能暗中破坏了表达式的结构，从而使之不符合 BNF 表述。此外，考虑到 String 是不可变对象，每次替换会造成额外的开销，而且字符串处理的代码普遍可读性较差，操作次数也较多。在阅读他人代码的过程中，也往往是在字符串替换和数据范围限制上发现问题。

那么，如果当初在设计时就考虑完备，完全不使用字符串替换会怎么样呢？别的部分不提，仅刨除 Scan 和 Expand 两个专门用替换进行预处理的类，那么：

显然，从 Rate 表项中可以看出优化效果显著。

总结：字符串替换害人害己。

字符串替换带来的便捷，早已在暗中标好了价格。

六、架构设计总结

6.1 面向过程 -> 面向对象

从面向过程到面向对象的转变是较为困难的，因为实际项目往往不是一个个独立的算法题。面对总是不断变化的实际需求，我们要尽量用同一份代码做最小的改动来应对。在我看来，这其实是抽象程度和可拓展性之间的博弈。以最简单的 a + b 为例：

// cpp
int a,b;
cin >> a >> b;
cout << a + b << endl;

// Java
public class Num {
    int val;
    public Num(int val) { this.val = val; }
    public int getVal() { return this.val; }
    public int add(int other) { return this.val + other.getVal(); }
}
public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        Num a = new Num(scan.nextInt());
        Num b = new Num(scan.nextInt());
        System.out.println(a.add(b));
    }
}

仅从纯粹的结果导向来看，我只需要一个32位数值 a，那么面向过程做法就纯粹地用了一个32位变量 a 来进行维护，简单干脆。相比而言，面向对象做法会想办法告诉我 a 是谁（一个 Num 对象）、a 有什么属性（一个32位数值val）以及 a 能做什么（能获得数值 val、能做加法），复杂且多余。

可是如果从长远来看，没有注释，第一种面向过程的代码的生命周期是十分短暂的，大概率写完代码后过个几天自己都忘了它的功能以及与其它代码之间的联系了（当然，不是特指 a + b 这种简单程序，在程序复杂起来，几百上千行甚至更多时，写大量注释显然也是不可能的。此外，这种代码 debug 也很是头痛）。但从第二种面向对象的写法中，我们选择为解决某类通用的问题建立一种通用的结构，这便可以提高代码的复用性（譬如凡是数字相关的问题都可以用Num 类进行处理，虽然 Java 有 int 类型），这种做法的优越性会随着数据特征与行为的增加而越来越明显。

这也是我为什么称在表达式化简中率先使用面向过程程序设计是一种试错了。无论是解析表达式时有大量相似功能的堆砌代码，还是面对复杂字符串时陷入细节泥沼招致的频发 Bug，都让我心力憔悴。这次是亲身体会到：代码行数上去了，可读性和可拓展性才是重中之重。

6.2 重构 & 补丁

能补就补，不能补就重构

事实证明，好的架构完全可以从容不迫地应对需求变更，而重构 & 补丁均是维护一个良好架构的手段。

我们在设计架构时，往往需要预测未来的需求变动，对于可预测的需求变化方向，必须提前考虑在内才能尽可能保持良好的可拓展性（比如表达式化简中的括号嵌套与新增三角函数）。

而对于不可预测的那部分（比如表达式化简中的自定义函数与求和函数），首先应考虑原架构的逻辑与新需求是否兼容。如若不兼容，则说明之前对需求预测的方向 “ 跑偏 ” 了，需要及时根据新增的已知需求预测新的需求变化趋势设计新架构并进行重构。如果新需求与原架构是兼容的，那么既可以为新需求建构新的架构再整合至原架构（比如可以设计一个专门的函数类，为所有函数进行统一构建），也可以选择在原架构的基础上缝缝补补（新增函数 = 新增类）。至于具体如何选，则要看新需求和已实现需求之间的共性多寡，共性多则重构，共性少则打补丁（此类判断要结合主客观因素共同决定，多靠经验）。