OO第一单元总结：表达式求导

一、问题描述

　　三次作业的内容均为多项式求导。第一次仅有幂函数，第二次添加了三角函数，第三次增加了嵌套因子。在格式输入和计算过程中，前两次都有较为固定统一的格式，而第三次由于有嵌套的递归表达，如果前两次没有专注设计（泪目）则需要尤其调整结构的问题。

二、程序设计

　　整个问题可以被拆分为格式检查、求导计算和输出处理三部分。其中格式检查和构造数据结构是比较类似的过程，但为了方便测试和调试被我单独分成了两个模块（放在一起可能会节省不少工作量）。

格式检查：拆分正则表达式

　　格式除了常规的匹配之外，需要注意的点有：空输入与特殊符号、指数符号及绝对值、表达式因子的括号等。

　　由于空白字符情况较一般而写起来比较麻烦，在开始匹配之前首先排除掉空白字符的错误情况，然后去掉它们。特殊字符同理，先整体判一遍合法字符集。

　　第一次：第一次正则表达式比较简单，但由于字符串较长，大正则有爆栈风险（非捕获组能有效降低该风险）。项的分割较为明确——运算符号，可以通过运算符号顺序逐项匹配。

　　第二次：增加了三角和乘号。与第一次同样的运算符分割。

　　第三次：采用了栈的方法来匹配括号，两括号之间的字符串交给第二次作业一样的方法来处理。

求导计算

前两次：求导都能得到固定的格式（尤其第一次），求导只需要变换类里相应参数（但可扩展性基本为0），也方便优化。

　　第三次：通过链式法则构造了一颗表达式树。

类的设计

　　第一次：类为项，只系数和指数两个参数；

　　第二次：类包含系数、三角指数和幂指数，以及求导完成后多出来的三项新的自身项（直接公式求导）；

　　第三次：为了方便求导（懒），与表达式有关的类只有最细的因子，使用标记区分四种算符因子、四种项因子及其指数，并分别设置访问和修改方法。

数据结构

　　前两次：由于结构简单，为了便于优化采用的一维数组；

　　第三次：由于增加了嵌套而采用了表达式树：树的构建过程还是用栈（逆波兰表达式），树的分支节点为四种运算符——加减乘以及复合。其中，为了统一化，将形如 (...) 的表达式看作x与括号内表达式的复合，不需要单独处理括号问题。树的叶节点则为因子。第三次的二叉树结构，把叶节点拆分到只剩最小的因子的好处是便于计算，但缺点在于树的构成会十分不平衡，树的层数很大。作业中由于表达式较短，树的层数不会很深，但求导之后的层数也已经很可观。事后我想到的优化结构的思路是使用多叉树管理并列项。

求导过程

　　前两次：公式直接求导；

　　第三次：通过二叉树递归求导。+、-求导左右儿子；复制自身，两个指向同一父节点（+）然后分别求导左、右儿子；复合符号根据链式法则在父节点复制自身后求导。