buaa面向对象第一单元
2023-03-16 15:31 由
clapp 发表于
#后端开发
面向对象设计与构造第一单元
问题：表达式的化简
- 表达式中仅含有\(x,y,z\)三种未知数
- 表达式仅含有\(+,-,*,**,\sin,\cos,dx,dy,dx\)几种运算
- \(dx,dy,dz\)分别表示对\(x\)求导，对\(y\)求导，对\(z\)求导。
- **表示乘方，例如\(2**3=2^3=8\)
- 包含若干自定义函数。
- 化简后的结果除必要括号(三角函数运算符号带的必要括号)外不含其他括号。
架构设计
对于表达式的问题很自然就会想到用栈去处理。
定义运算符的优先级。
| 运算符 |
优先级 |
| ) |
0 |
| +、- |
1 |
| * |
2 |
| ** |
3 |
| ( |
4 |
首先考虑如果表达式中不含字母只含数字应该如何计算。考虑双栈结构按照如下流程处理
(这里仅讨论主体架构，关于细节方面就不再赘述)。
flowchart LR
node_1["读取"]
node_2{"判断"}
node_3["压入数字栈"]
node_4["压入符号栈"]
node_5{"优先级#lt;=符\n号栈顶元素"}
node_6["数字栈pop\n数字栈pop\n符号栈pop"]
node_9["将出栈的三个元\n素进行运算并将\n结果压入数字栈"]
node_11{"符号栈空?"}
node_7{"符号栈顶为(？"}
node_8{"当前符号为)?"}
node_10["符号栈pop"]
node_1 --> node_2
node_2 --"数字"--> node_3
node_3 --> node_1
node_2 --"运算符"--> node_5
node_5 --"NO"--> node_4
node_4 --> node_1
node_5 --"YES"--> node_11
node_11 --"YES"--> node_4
node_6 --> node_9
node_9 --> node_5
node_7 --"NO"--> node_6
node_11 --"NO"--> node_7
node_7 --"YES"--> node_8
node_8 --"NO"--> node_4
node_8 --"YES"--> node_10
node_10 --> node_1
对于求导运算与三角函数运算，他们都是单元运算，并且运算作用范围必有一对()，
因此当符号栈顶为求导运算和三角函数时直接取出计算即可。
PS:有关自定义函数的处理，我采用了一种比较简单直接的办法——字符串替换。即把实参截取出来将函数表达式中的形参替换掉。
我们仔细思考用栈计算表达式的流程，容易发现其只关心表达式的运算结果而并不关心表达式的层次结构。
所以后续的作业关键点就转换成了如何用合理的数据结构表示运算结果。
第一次作业当中不含三角函数、自定义函数以及求导，因此输出结果仅表现为若干单项式的和。
于是用单项式组合成多项式的结构并定义单项式类及多项式类的加法乘法就能很轻松的解决。
第二、三次作业引入了三角函数，上述结构便不再适用了。
引入三角函数之后的难点在于三角函数之间的相互嵌套。这种互相嵌套的结构类似于树结构，于是我们考虑用类似表达式树的结构表示运算结果。
每个树结点记录两个信息：
- 此结点所表示子树的运算结果外是否需要再加上一个三角函数运算。
- 此结点的所有儿子结点之间的运算关系。(叶子结点忽略)
对于叶子结点只需记录此结点对应的多项式(即将第一次作业的设计封装进去)
例如树
flowchart TB
node_1(("null\n+"))
node_2(("sin\n+"))
node_3(("cos\n*"))
node_4(("x<sup>2</sup>*y"))
node_5(("z"))
node_6(("x*z"))
node_7(("y"))
node_8(("x<sup>4</sup>"))
node_1 --- node_2
node_1 --- node_3
node_2 --- node_4
node_2 --- node_5
node_3 --- node_6
node_3 --- node_7
node_3 --- node_8
即表示表达式\(\sin(x^2*y+z)+\cos(x^4*x*z*y)\)
接下来只需要定义两棵树之间的加法和乘法。
两棵树的加法：
flowchart TD
node_1[/"a"\]
node_2[/"b"\]
node_3(("null\n+"))
node_4[/"a"\]
node_5[/"b"\]
node_3 --> node_4
node_3 --> node_5
两棵树a,b的乘法：
- 如果其中一棵树a根结点具有"null +"的形式，则新建一个根结点\(root\)，将a根结点的每个子结点与b做乘法的结果作为\(root\)儿子结点。\(root\)所代表的树就是运算结果。
- 如果两棵树都具有"null +"形式，则需要将a,b根结点的子结点两两相乘。
- 如果都不具有"null +"形式，则简单模仿树的加法进行处理即可。
- 叶子结点需要特殊处理，调用第一次作业当中写好的多项式乘法即可。
当然仅仅只做好树的乘法和加法是不够的，因为这还无法实现化简的目的。为此，我们还需要做以下约定：
- 对于具有"null +"形式的结点，若其只有一个儿子，则用儿子替代这个结点。
- 对于具有"null *"形式的结点，不允许其儿子中出现"null +"。
加入求导因子后，只需按照求导法则为树建立求导方法即可。
合并同类项(树哈希)
- 一般合并同类项有两种思路
- 逐字符的比较判定。
- 为每个表达式建立哈希值。
- 但是前者操作比较繁琐且时间复杂度较高，后者如果没有较好的冲突处理机制则很容易被hack。
- 逐字符比较复杂度高的原因就是有大量的重复比较，我们考虑如何减少这种重复比较。
- 由于这次作业我是用树构建的，下面介绍一种关于树的哈希方法，值得一提的是这种哈希方法不会产生冲突。
为了简单起见，下面以一棵普通的无根树为例
flowchart TB
node_1((" "))
node_2((" "))
node_3((" "))
node_4((" "))
node_5((" "))
node_6((" "))
node_7((" "))
node_8((" "))
node_9((" "))
node_10((" "))
node_11((" "))
node_1 --> node_2
node_1 --> node_3
node_1 --> node_4
node_2 --> node_5
node_2 --> node_6
node_3 --> node_7
node_4 --> node_8
node_4 --> node_9
node_9 --> node_10
node_9 --> node_11
从叶子结点开始，我们给每个特定的结构一个唯一的编号。
flowchart TB
node_1((" "))
node_2((" "))
node_3((" "))
node_4((" "))
node_5(("1"))
node_6(("1"))
node_7(("1"))
node_8(("1"))
node_9((" "))
node_10(("1"))
node_11(("1"))
node_1 --> node_2
node_1 --> node_3
node_1 --> node_4
node_2 --> node_5
node_2 --> node_6
node_3 --> node_7
node_4 --> node_8
node_4 --> node_9
node_9 --> node_10
node_9 --> node_11
往上一层出现了两种新的结构，
flowchart TB
node_1((" "))
node_2(("1"))
node_3(("1"))
node_4((" "))
node_5(("1"))
node_1 --> node_2
node_1 --> node_3
node_4 --> node_5
我们给他们标号为2，3
flowchart TB
node_1((" "))
node_2(("2"))
node_3(("3"))
node_4((" "))
node_5(("1"))
node_6(("1"))
node_7(("1"))
node_8(("1"))
node_9(("2"))
node_10(("1"))
node_11(("1"))
node_1 --> node_2
node_1 --> node_3
node_1 --> node_4
node_2 --> node_5
node_2 --> node_6
node_3 --> node_7
node_4 --> node_8
node_4 --> node_9
node_9 --> node_10
node_9 --> node_11
又出现了新的结构
flowchart TB
node_1((" "))
node_2(("1"))
node_3(("2"))
node_1 --> node_2
node_1 --> node_3
编号为4
flowchart TB
node_1((" "))
node_2(("2"))
node_3(("3"))
node_4(("4"))
node_5(("1"))
node_6(("1"))
node_7(("1"))
node_8(("1"))
node_9(("2"))
node_10(("1"))
node_11(("1"))
node_1 --> node_2
node_1 --> node_3
node_1 --> node_4
node_2 --> node_5
node_2 --> node_6
node_3 --> node_7
node_4 --> node_8
node_4 --> node_9
node_9 --> node_10
node_9 --> node_11
最后给结构
flowchart TB
node_1((" "))
node_2(("2"))
node_3(("3"))
node_4(("4"))
node_1 --> node_2
node_1 --> node_3
node_1 --> node_4
编号为5
flowchart TB
node_1(("5"))
node_2(("2"))
node_3(("3"))
node_4(("4"))
node_5(("1"))
node_6(("1"))
node_7(("1"))
node_8(("1"))
node_9(("2"))
node_10(("1"))
node_11(("1"))
node_1 --> node_2
node_1 --> node_3
node_1 --> node_4
node_2 --> node_5
node_2 --> node_6
node_3 --> node_7
node_4 --> node_8
node_4 --> node_9
node_9 --> node_10
node_9 --> node_11
至此，所有不同的树结构都有了一个独一无二的编号，我们就可以很方便的依据这个编号合并同类项了。
但是本人并没有在作业中实践这个树哈希，只是口胡了一下，感觉为了这点性能分不是很有必要，也没有什么意思，遂润去cf、atc玩耍。
PS:此方法也可以用来判定两棵无根树同构，方法是找到两棵树的重心并以重心为根进行树哈希（由于树可能有两个重心，所以最坏情况下要做四次。）
bug分析
- 这轮作业基本没什么bug，第一次作业被hack了一下，是理解错题意了，以为字母前面也可以带一个符号。
- 第三次作业强测WA了一个点是因为新增的求导方法写的比较快，忘记满足上面说的第二条约定了。
重构
- 这三次作业我并没有任何的重构，都是不断增量开发直至最终成形。
互测
- 我没有特意阅读别人代码去刀人，感觉之前在codeforces和UOJ上都快玩腻了，就不是很有兴趣，就是无聊的时候随手交几个比较简单的数据玩玩，但没想到还真刀中了一个，我记得那个数据是sin(sin(0)**0)答案应该是sin(1)但那个xd输出了0，估计是卷性能分反而卷错了(樂)。
一些想法
作为没有选先导课，寒假又完全没有预习的人（其实寒假买了大黑书的，但直到开学它都还是崭新的bushi）刚开始对于不会java还是有点慌的，但是好在编程语言之间的本质都是相通的，我对C/C++也比较熟悉，于是看了1个多小时java语法遂上手开始写代码。
于是就出现了辛辛苦苦写完了一个方法，却被告知是java库里自带的。。。(卒)
很奇怪的一点，作业开始之前所有人都告诉我不要用栈去写，根本写不出来。但是实际上我写下来并没有感觉到什么阻力，而且用栈写考虑的重点就只有多项式的乘法加法，第二次作业就变成树的乘法加法，第三次作业就加个树的求导。这样的思路不是应该比什么递归下降又是term又是factor又是expr的设计更自然更简单嘛。
还有一种说法是栈并不能体现表达式的层次结构，我觉得也不尽然，栈并非不体现层次结构，而是把层次结构表现在计算结果中了。
因此，我并不觉得表达式求值适合作为面向对象的作业，我觉得一切架构的设计都是为了让问题变得简单，使问的本质更加清晰。
而表达式求值的本质已经足够简单清晰了，再去拼命想所谓精妙架构反而会使问题复杂化。建万丈高楼需要稳固的脚手架，但是搭玩具积木再这么做就完全没有必要。
不管是面向过程、面向对象还是面向函数，任何编程模式的设定都是为了简化问题，解决问题就是要回归到问题本身具体问题具体分析，把表达式作为课程的作业就有为了面向对象而面向对象之嫌。
华罗庚说过数学就是要足够的退退到原始而又不失本质的地方，我觉得程序设计也是如此，既然栈--树的设计已经触及到了问题的本质，那就不必反其道而行之。
说实话，对于本人来说，这次作业写下来着实有些无聊，题目也显得过于稀松平常，略有挑战的地方在于代码规模，以前写过最长的代码就是200行左右的Link-cut-tree、动态DP、树套树之类的玩意。这次作业总代码量已经有800+行，但写完之后完全没有写出上述算法之后的喜悦感和成就感，感觉只是完成了课程的一个任务罢了。
另外，年年表达式、年年电梯，难道不腻吗，是不是该换换题了呢？
热门相关：地球第一剑 网游之逆天飞扬 天启预报 天启预报 薄先生，情不由己