BUAA_OO第一单元总结性博客作业——表达式求导 / 四六文摘

一、程序设计思路在我的三次作业中都采用了类的分层结构，采用逐项匹配，分层求导的思路。（一）、第一次作业中构建了Polynimial（多项式）类，在类的构造器中就完成了对非法空格的判断并对合法表达式进行删除空格处理。由于第一次作业仅含有带有系数的幂函数与常数项，因而我就没有专门构建针对每一个项的类，而是在本类中就定义了getitem方法，用正则表达式逐项匹配出符合要求的项。在第一次作业中我求导的基本单位为项，在构造正则表达式时我对表达式中可能出现项的类型进行枚举，分别为：（1）系数与指数均有的幂函数，（2）仅有系数的幂函数，（3）仅有指数的幂函数，（4）无指数，无系数的幂函数(x)，（5）仅为常数；每一次调用getitem方法时，从表达式开头按顺序寻找符合要求的项，将它抠出来并分别进行求导操作，逐项输出返回至main函数所在类。并在main函数所在类中完成合并同类项、化简输出的操作。（二）、第二次作业较第一次作业增加了三角函数因子，并且改变了项中因子的构造。在第一次作业中可以视为幂函数的系数的常数因子，在第二次作业中必须作为一个单独的因子来处理。比如在第一次作业中仅会出现3*x^2类型的项，这时其中的系数“3”可以看作是3*x^2幂函数的一部分，与幂函数合并处理，而在第二次作业中可能会出现3*3*x^2这种类型的项，这时若将第一个”3“当作常数因子来处理，将第二个”3“仍然当作幂函数的系数来处理，整个类的构造就显得拖沓、臃肿，因此我将这个项中的两个”3“均当作一个常数因子来处理，即为取消了第一次作业中的带有系数的幂函数因子，在第二次作业中的幂函数仅有x与x^n两种。为了简化第二次作业的设计，在第二次作业中我设计的求导方法的基本单位仍然为项，这也为第三次作业埋下了先天缺陷。同样地，在第二次作业中，我也采用了逐项匹配的思路。我构造了一个针对每一项的正则表达式：1 String itemregex =2 "([-+]?)" + "(" + // 正负号用于连接item3 "(\\*(sin|cos)\\(x\\)\\^[-+]?\\d+)|" + // 因子5 有指数的正弦函数4 "(\\*(sin|cos)\\(x\\))|" + // 因子4 无指数的正弦函数5 "(\\*x\\^[-+]?\\d+)|" + // 因子3 有指数的幂函 6 "(\\*x)|" + // 因子2 无指数的幂函数 7 "(\\*[-+]?\\d+)" + // 因子1 带符号整数8 ")+";可以看出，每一项均由以”*“为开头的5种因子构成，但是在每一项的开头那个因子，比如3*3*x^2这个项中的第一个带符号整数因子”3'的前面并没有“*”，这种情况怎么将第一个因子匹配进去呢？在这里面我想说明我处理开头因子时的一个小trick。根据指导书上的文法介绍，每一项的开头可能有1个、2个、3个连续的正负号。当开头有三个连续符号时，紧接着的因子必须是常数。在Polynomial类中我设计了一个modifybegin的方法，第一步，当表达式开头无符号，则添上一个正号；当表达式开头有三个符号时，将前两个符号等价处理为一个符号；当表达式开头有两个符号时，若第三个字符是数字，则不处理，若第三个字符不为数字，则将前两个符号合并；当表达式开头只有一个符号，不处理。第二步，在表达式的第一个符号后面塞进去一个”*“。这样，若一个含有两个因子表达式为“+++1*+1，++x*+1，++1*+1，+1*+1，”，第一步处理完为“++1*+1，+x*+1，++1*+1，+1*+1”，第二步处理完为“+*+1*+1，+*x*+1，+*+1*+1，+*1*+1”。我们可以把处理表达式理解为，第一个乘号前面的正负号为连接符，第一个乘号后面的正负号为带符号整数的符号。可以看出，经过处理的表达式，“*”号的个数与因子个数相等，即处理了文法，避免了形似“+++1”类型项的特判，又方便了每个因子的匹配，避免了为第一个因子专门书写正则表达式的繁琐。这个方法我沿用到了第三次作业中。匹配到一个项后，就进入Item类中进行求导运算，Item类以a*x^b*sin(x)^c*cos(x)^d形式来存储每一个项，并进行求导运算，返回一个Arraylist<Biginteger[]>类型的二维数组，存储求导后的每一项以及每一项中的abcd值，再以bcd的合并作为key在HashMap中存储每一项，同时进行合并同类项操作，最后转化为String类型输出结果。（三）第三次作业较第二次作业增加了嵌套因子与表达式因子，虽说增添的因子的类型不多，但这也意味着不能用前两次作业那种投机取巧方法来处理多项式了，于是我在继承前两次作业的Polynomial类与Item类的基础上，花了大量时间在构造因子类上orz。我构造了一个父类Factor，包含一个String类型的值factor与一个基本的方法getFactors()，一共7个子类全部继承自Factor，除常数与符号类外其他类都各自定义了求导方法，两个含有嵌套表达式的类还定义了自己的取值方法getvalue()。Fuhao存储表达式开头的符号Const存储常数因子PowerF存储表达式因子TrigF存储三角函数因子TrigNest存储三角函数嵌套因子的函数名与嵌套的表达式ExpressionF存储表达式因子嵌套的表达式Term存储嵌套表达式中的每一个项

同样地，第三次作业我还是采用逐项匹配的思路，只是在第三次作业中我采用了逐因子匹配，在getitem方法中，先一个因子一个因子地匹配，匹配完一个项,返回一个名为itemfactor的Arraylist<Factor>类型数组；若匹配到了嵌套因子开头或表达式因子开头，则重复调用getitem方法，在嵌套因子中继续匹配表达式，直到遇到“）”返回，将返回的Arraylist<Factor>数组储存到ExpressionF类或TrigNest类中的contains数组，再将ExpressionF类或TrigNest类储存到itemfactor中，itemfactor即为这一项包含的所有因子内容，进入Itemdao类求导运算，再逐因子匹配下一个项，直到表达式完成。ArrayList<Factor> itemfactor = new ArrayList<>(); String trigfuncregex = "\\*(sin|cos)\\(x\\)(\\^[-+]?\\d+)?"; //三角函数因子 String powerfuncregex = "\\*x(\\^[-+]?\\d+)?"; //幂函数因子 String constantregex = "\\*[-+]?\\d+"; //带符号整数因子 String trigfuncnestregex = "\\*(sin|cos)(\\()"; //带嵌套因子的三角函数开头 String expressionbeginregex = "\\*(\\()"; //表达式因子开头在Item类中，逐项遍历Arraylist<Factor>中的每一个Factor，调用这个Factor的求导方法与其他所有Factor的getvalue()方法，将返回值用“*”连在一起并输出，就是针对当前项的求导结果，若遇到的是一个嵌套因子，则补上左右括号并在内部递归求导，最后返回String类型的求导结果至Polynimial类中，再由Polynomial类返回至main函数输出。在对输出的优化处理中，我将输出项含有“0”因子的项直接丢弃，具体实现方法是在求导过程中，若求导后输出结果为0（一般出现在常数求导中），则直接中断这个for循环，不将针对这一项的求导结果合并到result字符串中，这样可以避免后期处理过程中可能出现的判断错误。二、程序结构分析：

各类总代码规模：（Statistic）:Source FileTotal LinesSource Code inesComment LinesBlank LinesFuhao.java171304Factor.java171304Const.java11902ExpressionF.java878007PowerF.java545004Itemdao.java11410608TrigNest.java14613808Term.java14613808TrigF.java767204Homework3main.java272232Polynomial.java255231915复杂度分析(class)[Metrics]：classOCavgWMChomeworkthree.factor.Const1.02.0homeworkthree.factor.ExpressionF6.7527.0homeworkthree.factor.Factor1.03.0homeworkthree.factor.Fuhao1.03.0homeworkthree.factor.PowerF3.333333333333333510.0homeworkthree.factor.Term7.33333333333333344.0homeworkthree.factor.TrigF5.015.0homeworkthree.factor.TrigNest6.33333333333333338.0homeworkthree.Homework3main3.03.0homeworkthree.Itemdao6.030.0homeworkthree.Polynomial4.16666666666666750.0Total 225.0Average4.687520.454545454545453复杂度分析(method)[Metrics]:methodev(G)iv(G)v(G)homeworkthree.factor.Const.Const()1.01.01.0homeworkthree.factor.Const.Const(String)1.01.01.0homeworkthree.factor.ExpressionF.dao()9.010.011.0homeworkthree.factor.ExpressionF.ExpressionF(ArrayList)1.01.01.0homeworkthree.factor.ExpressionF.getContains()1.01.01.0homeworkthree.factor.ExpressionF.getvalue()1.011.016.0homeworkthree.factor.Factor.Factor()1.01.01.0homeworkthree.factor.Factor.Factor(String)1.01.01.0homeworkthree.factor.Factor.getFactors()1.01.01.0homeworkthree.factor.Fuhao.Fuhao()1.01.01.0homeworkthree.factor.Fuhao.Fuhao(char)1.01.01.0homeworkthree.factor.Fuhao.getfuhao()1.01.01.0homeworkthree.factor.PowerF.dao()7.08.08.0homeworkthree.factor.PowerF.PowerF()1.01.01.0homeworkthree.factor.PowerF.PowerF(String)1.01.01.0homeworkthree.factor.Term.dao()4.012.016.0homeworkthree.factor.Term.fdao(Factor)7.07.07.0homeworkthree.factor.Term.fvalue(Factor)7.07.07.0homeworkthree.factor.Term.gettermContains()1.01.01.0homeworkthree.factor.Term.getvalue()1.09.014.0homeworkthree.factor.Term.Term(ArrayList)1.01.01.0homeworkthree.factor.TrigF.dao()12.09.013.0homeworkthree.factor.TrigF.TrigF()1.01.01.0homeworkthree.factor.TrigF.TrigF(String)1.01.01.0homeworkthree.factor.TrigNest.dao()10.015.017.0homeworkthree.factor.TrigNest.getContains()1.01.01.0homeworkthree.factor.TrigNest.getinsidevalue()1.011.016.0homeworkthree.factor.TrigNest.getvalue()1.04.04.0homeworkthree.factor.TrigNest.getZhishu()1.01.01.0homeworkthree.factor.TrigNest.TrigNest(String,ArrayList,BigInteger)1.02.02.0homeworkthree.Homework3main.main(String[])1.04.04.0homeworkthree.Itemdao.dao()4.012.016.0homeworkthree.Itemdao.fdao(Factor)7.07.07.0homeworkthree.Itemdao.fvalue(Factor)7.07.07.0homeworkthree.Itemdao.Itemdao()1.01.01.0homeworkthree.Itemdao.Itemdao(ArrayList)1.01.01.0homeworkthree.Polynomial.dealsin(ArrayList,ArrayList,Matcher)1.04.04.0homeworkthree.Polynomial.deletespace()3.07.013.0homeworkthree.Polynomial.deletestr(String)1.01.01.0homeworkthree.Polynomial.geteachitem(ArrayList,Matcher,Matcher,Matcher,Matcher,Matcher)6.012.012.0homeworkthree.Polynomial.getitem()4.08.08.0homeworkthree.Polynomial.getlength()1.01.01.0homeworkthree.Polynomial.judgent(int,int)1.03.04.0homeworkthree.Polynomial.judgesincosbegin()1.06.06.0homeworkthree.Polynomial.modifybegin()1.013.016.0homeworkthree.Polynomial.Polynomial()1.01.01.0homeworkthree.Polynomial.Polynomial(String)1.08.08.0homeworkthree.Polynomial.sepitem()1.02.02.0Total122.0221.0261.0（一）、Polynomial类名称规模属性pono1方法sepitem9deletespace5modifybegin32getlength3judgesincosbegin12judgement11dealsin30geteachitem42getitem40deletestr4

（二）、Itemdao类名称规模属性item1方法 dao53fdao17fvalue17

（三）、package factor 中的类

（四）、程序结构优缺点分析优点：层次清晰，分为表达式、项、因子，共三层，仅在因子这个层次实现求导方法，易于拓展。缺点：递归求导时迭代层数较多时，由于需要迭代构造几个Term类，程序速度较慢，易出现TLE情况；Factor层返回Item层，Item层返回Polynomial层时，由于储存时使用的是Arraylist，而返回时需要得到String类型的value，在Arraylist向String转化的过程中对于符号的处理易出错，且一旦出错，由于层次迭代较多，难以找到原因，且输出结果也难以优化。三、历次作业bug分析（一）、第一次作业1个bug，类型：优化出错指数为1时输出忽略指数，但是忘记把幂的符号"^"去掉了，，，时刻警醒（二）、第二次作业1个bug，类型：空格处理错误对于指数中的带符号整数的非法空格判断，我将正则写成了String regex3 = "(sin\\(x\\)|cos\\(x\\)|x)"+"[\\s]*[\\^][\\s]*[+-][\\s]+[0-9]+";这样当sin(x)与指数的符号与数值间同时出现非法空格时无法判断，需要修改为如下正则修复bug。String regex3 = "[\\^][\\s]*[+-][\\s]+[0-9]+";（三）、第三次作业3个及以上bug，写码一时爽，公测火葬场。（1）x^0以及x^1求导的bug（出现在package.factor.PowerF中）当幂函数无指数时，我对它的求导输出结果为1，这是对的当幂函数有指数时，我为了简化输出，指数为0的时候输出1，指数为1的时候输出x，（第一眼看去好像没什么不对。解决办法：改了两个字符搞定。（2）当函数里头递归嵌套一个因子时，比如sin((x+x))这种嵌套因子求导时，我在输出时为了优化把对内部嵌套因子输出的括号给去了，求导结果是cos((x+x))*(1+1),为什么只有一层括号呢，因为我觉得如果里面是表达式因子，它会自带一层括号，我不用去考虑它。如果里头是一个非表达式因子，比如sin(x^2),求导完就是cos(x^2)*2*x，看起来也没什么不对，对吧？那么，再难一点，如果是这样子，sin(cos(x)),这样输出结果就有负号啦，会不会出事呢？看看结果，cos(cos(x))*-1*sin(x)，咦？没事儿？万事大吉啦。（我在提交之前测试的时候就想到了这一步）提交之后，让我们来求一求sin((x+1))*(x+1)，结果是啥？cos((x+1))*(1)*x+1+sin((x+1))*1，emmmmmmm，凉凉。解决办法：对于Term类的求导或者取值的输出结果，我通通给他裹上一个括号，优化？不存在的，（在对Term类dao()与getvalue()方法的输出加个判断就好了，一行搞定）（3）CPU_TIME_LIMIT_EXCEED（这是个神仙bug我想说我的代码还小，它不是不行，它只是需要时间。在问了周围一票人都用的什么方法求导之后，我发现大家全是递归，那么为什么他们递归就那么快呢？于是我用debug认真一步一步跑了一下我的程序，发现是我的存储架构的天生缺陷……前面已经说了我用的是ArrayList<Factor>存储的每个项，遇到嵌套因子就将嵌套因子内部的表达式（因子）也存成一个ArrayList<Factor>,再将这个ArrayList存到一个嵌套因子类中，再将这个嵌套因子类存回原来的Factor，这就构成了一个链或者可以说是一棵树。用ArrayList本身就已经占有了一些时间了，更奇葩的是我的存储方式解决办法：我在用getitem()返回一个ArrayList后，不知道为什么抽了又新建了一个Term类去存这个东东，这也就意味着，我嵌套因子中的每一项，都是一个Term类。这样子结构看着舒服了，但是求导的时候，递归迭代层数以O(2^n)规模蹭蹭往上涨。。。跪了为了解决这个bug，我为了保住我的祖传代码，不对结构大动干戈，我专门写了个处理多余括号的方法，把外面的重括号去了，，，这样对于60个字符内的表达式，就很难TLE了。四、互测寻找别人bug策略在互测room开始前，（还不确定自己的代码够不够格进room之前），我先根据之前测试自己代码发现的bug，以及自己在代码架构时发现的几个易错点，整理出一份测试代码，上来先挑盲狙一遍。如果发现错了，交就完事了。如果没发现错，就找一个长一点的测试数据，用debug模式在对方代码上跑一遍，看下他代码的大体思路，找找正则有没有缺漏之初，或者一些很奇怪的地方认真琢磨一下，优秀就学习，不优秀的就叉他。五、应用对象创建模式分析我觉得这次三次作业中，大题对象能被分为3类：表达式、项、因子。最理想的写法，就是在第一二次作业中就直接抽象出因子的概念，将那些用乘号隔开的字符都化为一个因子类，再项一层就可以定义求导接口，在因子那一层进行求导操作，并回溯到项一层优化并输出，再回到表达式一层合并同类项并输出。如果第一次作业开始就有构造因子层的类，第二次与第三次作业仅仅只是丰富了类的数目而已，连求导方法都是已经定义了的，就可以大大简化第三次代码的工作量，但是，早知如此，何必当初呐……

BUAA_OO第一单元总结性博客作业——表达式求导

相关推荐