第一次作业

整体架构

整体架构
整体架构

形式化表述

原始规则

$$
\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 语言的认识，
也规范了代码书写风格，
整体来说受益匪浅

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。