BUAA_2022_OO_Unit1_Summary

本文主要是介绍BUAA_2022_OO_Unit1_Summary，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

第一次作业分析
- 思路分析
- 程序架构分析
  - 类图
  - 方法复杂度分析
  - 类复杂度分析
- Bug分析
  - 自己的Bug分析
  - Hack策略和结果
第二次作业分析
- 新增内容
- 迭代思路
- 程序架构分析
  - 类图
  - 方法复杂度分析
  - 类复杂度分析
- Bug分析
第三次作业分析
- 新增内容
- 重构历程
- 程序架构分析
  - 类图
  - 方法复杂度分析
  - 类复杂度分析
  - Bug分析
心得体会

还没从寒假的懒散惬意中摆脱出来，OO_Unit1便迎面袭来。

第一次作业分析

思路分析

我们要对一个包含加、减、乘、乘方以及括号（其中括号的深度至多为 1 层）的单变量表达式，输出恒等变形展开所有括号并化简的表达式。我的基本思路如下：

预处理消除多余的空格和连续的正负号('--' → '+','+-' → '-')。
先通过递归下降的方法将待解析表达式转换为表达式树结构（获得表达式结构）。

这里发现所有的基本因子（除Expr因子）都可转换为\(a * x ** b\)的形式，例如：

\[0 = 0 * x ** 0\\ 1 = 1 * x ** 0\\ x**3 = 1 * x ** 3\\ \]
因此，我引入了Unit这一基本单元用来表示\(coe * x ** pow\)，同时Expr和Unit统一实现Factor接口。
- 当解析到数字和幂函数时直接统一用Unit封装即可。（这里是为了方便合并同类项和计算，但同时也极大的降低了可拓展性，~~为后续的重构做出了重要贡献~~）
- 当识别到左括号可以生成一个新的Expr因子。
由此完成表达式树的构建。
递归解析生成的表达式树，最终生成一个ArrayList<Unit>用来存储解析表达式生成的所有基本单元Unit。

\[ArrayList<Unit>\space→ \sum a_i*x**b_i \]
- 表达式、项的基础组成逻辑如下：
\[Expr = trem\quad[\quad+ \quad terms\quad]*\\ term = Factor\quad[\quad* \quad Factor\quad]*\\ Factor = Unit\ \quad|\quad\ Expr\\ Unit = coe*x**pow\\ \]
- Expr遍历所有term，通过调用term.simplify()获取每一项的所有Unit，加入ArrayList<Unit>，然后根据表Expr自身的指数，连续自乘，获取最终的Unit列表。
- Term遍历所有的Factor，使得每个Factor互乘，由于存在Expr因子，因此每次互乘都需要遍历2个Factor乘子的Unit列表，完成2个ArrayList<Unit>的互乘，最后返回一个ArrayList<Unit>。这里需要注意的是，项具有正负，因此最后需要根据项的正负判断位positive，决定Unit列表是否需要进行系数翻转。
最后将得到的ArrayList<Unit>合并同类项化简即可。化简可以注意以下几点：
- 优先寻找正向因子并放到表达式首部，如:
  
  \[-1+x → x-1 \]
- cow为1或-1的因子可以省略输出"1*"，如：
  
  \[1*x**3 → x**3\\-1**x**6 →-x**6 \]
- pow为0的因子可以省略输出“x**0“，pow为1的因子可以省略输出"**1",pow为2的因子可以输出为“x*x",如：
  
  \[2*x**0→2\\x**1→x\\3*x**2→3*x*x \]
- cow为0的因子直接省略，但在此过程中需要避免化简出现的一些问题，如
  
  \[1*x**0\\0*x**2 \]
综上可以完成化简部分。

程序架构分析

类图

可以看到结构较为清晰，操作也较为简单，Expr和Unit实现Factor接口后可以分别重写simplify()实现化简。
但是由于使用Unit统一封装所有基本因子，降低了后续的可拓展性。

方法复杂度分析

getPolyFunc()、preProcessing()涉及化简、合并同类项，需要特判较多情况，因此复杂度较高
praseFactor()涉及判断各种因子的种类，导致复杂度的升高
大部分方法复杂度较低，且分布较为均匀

类复杂度分析

和方法复杂度同解释

Bug分析

自己的Bug分析

公测和互测均没有发现Bug。
- 自己虽然没有测出bug，但是不保证没有bug。
- 特殊判断太多，加入新的条件便需要改动太多地方，代码可读性较差，同时不便于后续迭代。

Hack策略和结果

Hack上主要通过自动生成大量随机数据轰炸和手撸边界数据。
- 代码实现(实现细节省略),构造思路也是利用递归下降生成表达式，通过合法性检测后方可Hack他人数据：
```
1.def getRanExpr(maxLen) -> str:
  *****************
2.def checkForLegal(expr) -> bool;
  *****************
3.import sympy
	project_dir = "C:\\**\\OO\homework1\\test"
  compare with sympy.sympify(expr)
  *****************
```
- 手动制造的一些数据：
\[边界：+-(-040000000*+81+-x**4*x**2)+-(+x*+3)**0\\ -+(+--0+-10)**+3-(-x**+2)**+1*(+-x+x**+0)**+1*x \]
\[特殊数据：(-x**2)*(-1)**0*(-1)**0\\ -(+x)**0+(-x**2)**1*(-1)**0*(x**1)**1*(0)**0 \]

\[化简易出错数据：11*x**0 + 2- +1*x**0-1*x*x+1*x**1 \]

最后发现别人几个bug：

Bug数据	Bug结果	Bug分析
(-x**2)(-1)0	x*x	在计算(-x2)生成-x2没考虑负号
2	2*	出现2x0时没考虑因子没有幂函数部分，因此不应该有号
(x-x)**+0	0	0**0的结果应为1

第二次作业分析

在屎山上建造一些新的房子，糟心程度可想而知。

出于懒惰，却往往不能达成目的。

新增内容

本次作业在上次的基础上增加了自定义函数，三角函数和求和函数，并且可允许括号的多层嵌套。由于我采用递归下降的处理方式，可以支持多层括号的嵌套。下面简单介绍一下我增量开发时采用的思路：

对于三角函数我定义为下：

\[(sin|cos)(a*x**b)**c \]
构建三角函数累TrigoFunc，用sign，factorCoe，factorPow，pow属性分别记录对应位置信息。
对于自定义函数类，我定义了CustomFunc类直接存储自定义函数，并替换成标准表达式(这种方式其实破坏了表达式的结构性，但是由于懒惰····）,基础思路如下：
- 该类的addCustomFunc方法读入一个自定义函数表达式，以 HashMap<String, ArrayList<String>> 的形式保存于该类中，索引为函数名，内容是函数的各个参数和表达式；
  
  \[f(x,y,z)=xy+y+z\Leftrightarrow<f,[x,y,z,xy+y+z]> \]
- 细节处理
  - 每次替换要整体带入，即将因子左右套上括号；
  - 对于f(y,x)的替换，先保护待替换变量x，防止其被重复替换
对于求和函数，我定义了求和函数类，通过字符串替换方式得到求和函数的等价表达式(这种方式其实破坏了表达式的结构性，但是由于懒惰·····)，形如\(sum(i,a,b,\alpha(i,x))\)的公式，我有以下处理思路：
- 将a,b转化为整数，判断上下界大小，如果\(a>b\),则返回0。
- 否则，通过循环得到字符串(如下)替换\(sum(i,a,b,\alpha(i,x))\)。
  
  \[( \alpha(a,x) + \alpha(a+1,x) + ······· + \alpha(b,x)) \]
- 细节处理：
  - 对于形如\(sum(i,a,b,i**2)\)的替换时需要需要注意替换为\((a)**2\)保证通过合法性检测；
  - 形如\(sum(i,a,b,sin(i))\)注意对sin中的i在替换时的保护
  - 求和函数的上下界应使用BigIneger以防止溢出(~~本人没考虑，导致第三次作业被无尽hack~~）

迭代思路

主体表达式部分已经根据我们的“预处理”，解决了自定义函数和求和函数的困扰。
lexer和praser部分增添对求和函数和三角函数的识别。
对于新的基本因子我们可以定义为：

\[Unit→a*x**b*\prod{sinFunc}*\prod{cosFunc} \]
因此我们可以这样定义Unit：

这样我们在解析到任何基本因子(除Expr外)都可以用Unit去包装，合并同类项也变的非常简单(重构已埋下根基)。

Unit新增toString()方法，方便简化输出形式较为复杂的Unit单元。
化简流程
- 特殊三角函数值的简化：
  
  \[sin(0)=0\space,cos(0)=1\\ sin(0)**0=1\space,cos(0)**0=1\\ sin(x**0)=sin(1),cos(x**0)=cos(1) \]
- 基于三角函数奇偶性的化简：
  
  \[sin(-f(x))**(2n+1)=-sin(f(x))**(2n+1)\space,sin(-f(x))**2n=sin(f(x))**2n\\ cos(-f(x))**a=cos(f(x))**a \]
- 特殊三角函数值合并：
  
  \[sin(a)**2+cos(a)**2=1\\ f(x)*sin(a)**2+f(x)*cos(a)**2=f(x) \]
还有一些更高阶的化简办法，例如动态规划实现\(sin(x)**2,cos(x)**2,1\)之间的转换、二倍角公式的使用····由于实力有限，没有在思考处理，实属遗憾。