「面向对象」Unit-1

第一次作业

整体架构

整体架构

形式化表述

原始规则

\[ \begin{align*} \texttt{Expr}\rightarrow\ &\texttt{White}\ [\texttt{PlusMinus}\ \texttt{White}]\ \texttt{Term}\ \texttt{White} \\ |\ &\texttt{Expr}\ \texttt{PlusMinus}\ \texttt{White}\ \texttt{Term}\ \texttt{White} \\ \texttt{Term}\rightarrow\ &[\texttt{PlusMinus}\ \texttt{White}]\ \texttt{Factor}\ |\ \texttt{Term}\ \texttt{White}\ \texttt{Multi}\ \texttt{White}\ \texttt{Factor} \\ \texttt{Factor}\rightarrow\ & \texttt{VarFactor}\ |\ \texttt{ConstFactor}\ |\ \texttt{ExprFactor} \\ \texttt{VarFactor}\rightarrow\ & \texttt{PowFuncFactor} \\ \texttt{ConstFactor}\rightarrow\ & \texttt{SignedInteger} \\ \texttt{ExprFactor}\rightarrow\ & \texttt{'('\ Expr\ ')'}\ [\texttt{White}\ \texttt{Index}] \\ \texttt{PowFuncFactor}\rightarrow\ & (\texttt{'x'}|\texttt{'y'}|\texttt{'z'})\ [\texttt{White}\ \texttt{Index}] \\ \texttt{Index}\rightarrow\ & \texttt{'**'}\ \texttt{White}\ [\texttt{'+'}]\ \texttt{LeadingZeroInteger} \\ \texttt{SignedInteger}\rightarrow\ & [\texttt{PlusMinus}]\ \texttt{LeadingZeroInteger} \\ \texttt{LeadingZeroInteger}\rightarrow\ & (\texttt{'0'}|\texttt{'1'}|\texttt{...}|\texttt{'9'})\{\texttt{'0'}|\texttt{'1'}|\texttt{...}|\texttt{'9'}\} \\ \texttt{White}\rightarrow\ & \texttt{WhiteChar} \\ \texttt{WhiteChar}\rightarrow\ & \texttt{'\textbackslash u0020'}\ |\ \texttt{'\textbackslash u0009'} \\ \texttt{PlusMinus}\rightarrow\ & \texttt{'+'}\ |\ \texttt{'-'} \\ \texttt{Multi}\rightarrow\ & \texttt{'*'} \end{align*} \]

• \(\{\}\) 表示允许存在 0 个、1 个或多个
• \([]\) 表示允许存在 0 个或 1 个
• \(()\) 内的运算拥有更高优先级，类似数学中的括号
• \(|\) 表示在多个之中选择一个
• 上述表述中使用单引号包裹的串表示字符串字面量，如 \(\texttt{'('}\) 表示字符 (

左递归

注意到 \(\texttt{Expr}\) 和 \(\texttt{Term}\) 生成式中存在左递归

\[ \begin{align*} \texttt{Expr}\rightarrow\ &\texttt{White}\ [\texttt{PlusMinus}\ \texttt{White}]\ \texttt{Term}\ \texttt{White}\\ |\ &\texttt{Expr}\ \texttt{PlusMinus}\ \texttt{White}\ \texttt{Term}\ \texttt{White}\\ \texttt{Term}\rightarrow\ &[\texttt{PlusMinus}\ \texttt{White}]\ \texttt{Factor}\ |\ \texttt{Term}\ \texttt{White}\ \texttt{Multi}\ \texttt{White}\ \texttt{Factor} \\ \end{align*} \]

转化为

\[ \begin{align*} \texttt{Expr}\rightarrow\ &\texttt{White}\ [\texttt{PlusMinus}\ \texttt{White}]\ \texttt{Term}\ \texttt{White}\ \texttt{ExprPrime} \\ \texttt{ExprPrime}\rightarrow\ &\texttt{PlusMinus}\ \texttt{White}\ \texttt{Term}\ \texttt{White}\ \texttt{ExprPrime}\ |\ \epsilon \\ \texttt{Term}\rightarrow\ &[\texttt{PlusMinus}\ \texttt{White}]\ \texttt{Factor}\ \texttt{TermPrime} \\ \texttt{TermPrime}\rightarrow\ &\texttt{White}\ \texttt{Multi}\ \texttt{White}\ \texttt{Factor}\ \texttt{TermPrime}\ |\ \epsilon \\ \end{align*} \]

去除空白字符

\[ \begin{align*} \texttt{Expr}\rightarrow\ &[\texttt{PlusMinus}]\ \texttt{Term}\ \texttt{ExprPrime} \\ \texttt{ExprPrime}\rightarrow\ &\texttt{PlusMinus}\ \texttt{Term}\ \texttt{ExprPrime}\ |\ \epsilon \\ \texttt{Term}\rightarrow\ &[\texttt{PlusMinus}]\ \texttt{Factor}\ \texttt{TermPrime} \\ \texttt{TermPrime}\rightarrow\ &\texttt{Multi}\ \texttt{Factor}\ \texttt{TermPrime}\ |\ \epsilon \\ \texttt{Factor}\rightarrow\ & \texttt{VarFactor}\ |\ \texttt{ConstFactor}\ |\ \texttt{ExprFactor} \\ \texttt{VarFactor}\rightarrow\ & \texttt{PowFuncFactor} \\ \texttt{ConstFactor}\rightarrow\ & \texttt{SignedInteger} \\ \texttt{ExprFactor}\rightarrow\ & \texttt{'('\ Expr\ ')'}\ [\texttt{Index}] \\ \texttt{PowFuncFactor}\rightarrow\ & (\texttt{'x'}|\texttt{'y'}|\texttt{'z'})\ [\texttt{Index}] \\ \texttt{Index}\rightarrow\ & \texttt{'**'}\ [\texttt{'+'}]\ \texttt{LeadingZeroInteger} \\ \texttt{SignedInteger}\rightarrow\ & [\texttt{PlusMinus}]\ \texttt{LeadingZeroInteger} \\ \texttt{LeadingZeroInteger}\rightarrow\ & (\texttt{'0'}|\texttt{'1'}|\texttt{...}|\texttt{'9'})\{\texttt{'0'}|\texttt{'1'}|\texttt{...}|\texttt{'9'}\} \\ \texttt{PlusMinus}\rightarrow\ & \texttt{'+'}\ |\ \texttt{'-'} \\ \texttt{Multi}\rightarrow\ & \texttt{'*'} \end{align*} \]

去多重加减符号

对于加减号，有四种可能：

• \(\texttt{Expr}\) 开头的正负号
• \(\texttt{Term}\) 开头的正负号
• \(\texttt{Factor}\) 中的正负号
• 连接 \(\texttt{Term}\) 的加减号

对于 \(\texttt{Expr}\) 开头的正负号，可以在其之前插入一个 \(0\) 将其转换为加减号。故只需要考虑后三种符号

注意 \(\texttt{Expr}\) 可能有多个开头（整个表达式开头，括号内部表达式开头）

根据多重符号化简规则，多重加减符号可以化简为单个加减符号，即

• 奇数个减号等价于减号
• 偶数个减号等价于加号

但是这里使用该化简式合法吗？

注意处理过后，第二类 \(\texttt{Term}\) 开头的正负号可以归并到第三类 \(\texttt{Factor}\) 中（由整个 \(\texttt{Term}\) 的正负变为修改第一个 \(\texttt{Factor}\) 的正负）

故只需要考虑如下两种情况

• \(\texttt{Factor}\) 中的正负号
• 连接 \(\texttt{Term}\) 的加减号

观察到，前者在 \(\texttt{parseFactor}\) 中作为因子符号来处理， 后者在 \(\texttt{parseExpr}\) 中作为分隔符被处理， 故可完美分离

当然，由于多重加减号本身地位相等，理论上也可以按照原来的表达式，读入并处理每一个加减号

\[ \begin{align*} \texttt{Expr}\rightarrow\ &\texttt{Term}\ \texttt{ExprPrime} \\ \texttt{ExprPrime}\rightarrow\ &\texttt{ExprPrime}\ \texttt{PlusMinus}\ \texttt{Term}\ |\ \epsilon \\ \texttt{Term}\rightarrow\ &\texttt{Factor}\ \texttt{TermPrime} \\ \texttt{TermPrime}\rightarrow\ &\texttt{TermPrime}\ \texttt{Multi}\ \texttt{Factor}\ |\ \epsilon \\ \texttt{Factor}\rightarrow\ & \texttt{VarFactor}\ |\ \texttt{ConstFactor}\ |\ \texttt{ExprFactor} \\ \texttt{VarFactor}\rightarrow\ & \texttt{PowFuncFactor} \\ \texttt{ConstFactor}\rightarrow\ & \texttt{SignedInteger} \\ \texttt{ExprFactor}\rightarrow\ & \texttt{'('\ Expr\ ')'}\ [\texttt{Index}] \\ \texttt{PowFuncFactor}\rightarrow\ & (\texttt{'x'}|\texttt{'y'}|\texttt{'z'})\ [\texttt{Index}] \\ \texttt{Index}\rightarrow\ & \texttt{'**'}\ \texttt{SignedInteger} \\ \texttt{SignedInteger}\rightarrow\ & [\texttt{PlusMinus}]\ \texttt{LeadingZeroInteger} \\ \texttt{LeadingZeroInteger}\rightarrow\ & (\texttt{'0'}|\texttt{'1'}|\texttt{...}|\texttt{'9'})\{\texttt{'0'}|\texttt{'1'}|\texttt{...}|\texttt{'9'}\} \\ \texttt{PlusMinus}\rightarrow\ & \texttt{'+'}\ |\ \texttt{'-'} \\ \texttt{Multi}\rightarrow\ & \texttt{'*'} \end{align*} \]

优先级

优先级从低到高分别为

• "+", "-"
• "*"
• "**"
• 括号内部表达式

按照不同优先级确定对象层次结构

• Expr

• Term

• Factor

• Base

  • VarBase
  • ConstBase
  • ExprBase

带括号的 \(\texttt{Expr}\) 可能作为 \(\texttt{Base}\)，需要注意这里的环状解析结构

括号结构包含的运算优先级最高，里面包含的 \(\texttt{Expr}\)，可直接作为子任务处理

计算与化简

计算

在按照优先层次生成表达式树后，需要从底向上进行计算

考虑引入计算类 \(\texttt{Monomial}\) 和 \(\texttt{Polynomial}\)， 分别负责单项式对象和多项式对象。

\(\texttt{Monomial}\) 形似于 \(a*x^{xindex}*y^{yindex}*z^{zindex}\)

在表达式树的每个节点上都将生成一个 \(\texttt{Polynomial}\) 对象， 按照不同节点的符号规则对子节点的 \(\texttt{Polynomial}\) 进行合并计算

根据不同的符号 \(\texttt{Polynomial}\) 需要支持加，减，乘，乘方

化简

计算过程中，可以顺便完成同类项的合并

\(\texttt{Polynomial}\) 使用 \(\texttt{TreeSet}\) 储存 \(\texttt{Monomial}\)，重写 \(\texttt{compareTo()}\) 函数从 \(\texttt{xindex}\) 到 \(\texttt{zindex}\) 依次比较

每次插入新项时，在已有项中查找是否有相同项，若有，取出并删除之，与新项合并后重新插入

实际上应该使用 \(\texttt{hashMap}\) 重写 \(\texttt{hashCode()}\) 和 \(\texttt{equals()}\)

最后输出的时候先输出正项，后输出负项，可优化开头的符号

后日谈

我喜欢不急不慢，有条不紊

我喜欢思路清晰，环环相扣

周五，正午，中测开始，我开始阅读任务书。 看看学长的博客，在草稿纸上写写画画，我觉得思路清晰，时间充裕

指尖微动，填坑变成补天，代码愈来愈繁杂

平日里接触的多的是竞赛中纯粹面向过程的代码，贫瘠的知识储备让我在不同架构间来回摇摆，不得要领

困难之处在于熟悉 Java 的设计思路，理解表达式解析中 处理/结果 的逻辑和维持代码量与可拓展性之间的平衡

对象打来电话，问我什么时候出发

「正在路上。」我说

摇摆间我决定推翻重构，将解耦进行到底

正如承诺般易得，也如承诺般沉重

周末上午十一点，向每一个 \(\texttt{Object}\) 真诚地许愿。过了

没有想到 OO 作业的压力确实不小，也可能是因为第一次接触花费了大量时间理解设计思路，也可能是自己实力不足，我几乎用了整个周末的时间完成代码，最后的结果也善乏可陈。 想想之后的生活，有些担忧，有些无奈

乐也对象，悲也对象，且战且走，且行且歌

第二次作业

整体架构

整体架构

自 HW-1 的重构

由 TreeSet 切换到 HashMap

新增功能

嵌套多层括号

原有架构中递归下降对括号的递归处理可以实现多层括号

自定义函数因子

1. 离线解析自定义表达式，使用 parseFuncDefine 生成 SelfDefFunc
2. 在生成表达式树时通过 parseSelfDefFunc 读取函数名和对应参数，生成 FuncBase，不继续往下解析
3. 使用 funcReplace 方法自底向上将所有的 FuncBase 代入 SelfDefFunc 生成对应的 Expr

三角函数因子

三角函数因子的解析和表达式因子比较像，难点在于三角函数不能简单的嵌入 单项式/多项式 结构，需要在单项式中增加三角函数项，而三角函数项中可能嵌套多项式，从而产生层级跳跃（类似于 Factor 和 Expr）

计算

Monomial 形似于 \(a*x^{p_x}*y^{p_y}*z^{p_z}*trigs\)

其中，\(trigs=\sin(Expr_{s1})*\cdots*\sin(Expr_{sn})*\cos(Expr_{c1})*\cdots*\cos(Expr_{cm})*\)

化简

带三角函数的 Monomial 的相等判断：

• 先判断函数名，再判断内部表达式，表达式结果递归处理
• 可以在这里卷一卷
  • \(\sin,\cos\) 奇偶函数性质
  • 三角函数合并公式

后日谈

做 OO 作业的过程很简单：

• 不断的思考
• 不断的测试
• 不断的推翻
• 不断的妥协

君 OO 本当上手

第三次作业

整体架构

整体架构

新增功能

嵌套自定义表达式

一边读取替换已处理的自定义函数即可

求导因子

注意单项式求导可能化为多项式

比较怪异的点是自定义函数需要对形参而不是实参求导，那么就必须在自定义函数定义时将求导符号消除

由于原先架构中解析/计算分离，自定义函数读取时只解析，不计算。在题目的强制要求下，只得在解析时额外提供一个求导类，并最后返回一个表达式类。

在解析时引入计算带来的问题并不止如此。由于不同的层次级别求导返回的结果不同，如 Expr 求导返回 Expr，而 Term 求导返回 Expr，Factor 求导返回 Term。在原本存在表达式因子，即 Factor(Expr) 的情况下，在这个架构上完成求导计算，会导致层级大大加深

这也从侧面应证了解析和计算分离的重要性

计算

考虑 Monomial 的求导

化简

略

后日谈

第一单元结束得很快，想起第一次作业平地起高楼被折磨得死去活来， 深刻地认识到了一个优秀的架构带来的迭代能力和稳定性

至少在这么多次的作业里，没有因为时间不够而遗憾离场，也没有思考不周而遭人背刺

后面的任务更多需要考虑思路，可能会轻松一丝吧

放 nm 的狗屁 --Unit2 完成后更新

架构设计

通过前期的调研，笔者确定了自己解析/计算分离的总体架构

其中，解析类只负责将表达式按照层次结构自顶向下转化为表达式树， 然后再使用计算类，自底向上完成表达式树的计算

在解析时，又根据运算的特点划分为多个层级， 后期增加新要求时迭代只需在对应层级新增类和方法， 减少上下层次间的交互

在设计过程中，只构建 不可变对象 的基本原则也笔者带来了很多方便

由于之前面向过程的思维还未除尽，常常复用同一个对象以提高效率。 常常会出现修改了 A 而改变了风马牛不相及的 B， 这给程序的调试和稳定性都带来了极大的挑战

故本次设计中，笔者全面采用了不可变对象的设计思路。 所有的对象一经创建即不再修改，所有的方法都返回一个新对象， 从而降低逻辑复杂度

bug 分析

由于良好的代码复杂度控制，在三次强测及互测中均未找到 bug

hack 策略

有如下几个关注点：

• 边界条件
• 优化和原有架构的交互
• 自己实现时的易错点
• 覆盖性测试

心得体会

整体来说，OO Unit 1 任务量很大。

因为没有经历 OO pre，缺乏面向对象设计的经验， 许多设计思路和技巧都需要不断翻阅学长的博客进行学习

由于懒，也没有手写测评机，也没有将随机取点判断相等的思路实装到代码里

卷优化的太多，小麻。 实际上大部分数据点涉及的优化都比较简单。 做优化的时候不能有太强的精神洁癖， 否则就会陷入思维泥泞中无法自拔

本次作业在架构上其实也有些遗憾， 不过本着能过且过的原则， 最终没有选择小重构， 这也是软件设计中常常出现的现象

午时已到

在三次作业完成过程中， 笔者加深了对于层次化设计和对 JAVA 语言的认识， 也规范了代码书写风格， 整体来说受益匪浅