写在前面
第一单元作业是针对输入的多项式进行格式合法判断,然后进行求导,结果长度优化,最后输出。三次难度递增,不断添加新的需求,总体感觉在实现方面没有多大困难(?),个人主要困扰环节是寻找自己未知bug阶段。
如果要挑出自己的错误,那此次最大的失误可能就是太相信自己的能力了吧。
自以为Java语言已经运用很娴熟,没必要跟着课程从字符再学一次(你在想x吃),同时过去自学过程中,遗落了正则表达式部分(讲道理我借的书们以及网课确实没提这玩意儿啊),导致第一次作业结束后,我盯着别人一百多行的代码问:“这是啥???”,看了看别人的正则表达式,又扫了扫自己的一万个if特殊判断,怪不得我会写六百多行。
到第二次作业我勉为其难地学了一点正则,用第一句的时候忽然发现,!,有点爽,然后就一直正则一直爽,判断格式用了二十多个正则表达式,作业结束后我又看着别人的一句长正则全部概括问:“这是啥???”
到第三次作业时,我已经将正则和if特例判断运用的炉火纯青,彼此相辅相成。
假的。
我同时用了一千行正则和一万个if。:-)
然后出现了1000*10000个漏洞。
第一次作业
看了看别人的总结,我这才明白第一次作业让做什么,大家都说是对简单多项式的求导,入门级难度不高,我也觉得。
都说难点在于对正则表达式的正确而熟练地使用。我就不一样了,我都没用正则(x)。个人认为,难点在于如何严谨地进行格式判断,而我运用了众多的if判断,并非是特例排除,而是层层剥减,最后将合法部分全部削去,若留下了空字符串则为合法。(你上文还写着是玩命覆盖特例呢喂!)
(要求概括)
对简单的幂函数多项式求导,只存在多项之间加减,无括号,每项由符号、系数、指数构成,这三个元素均非必须出现。
(个人思路)
听说用UML画图会使你想表达的程序结构更加直观?好的,如下图。
太直观了吧,很明显我只用了两个类(还包括一个主类)。
整个过程的实现十分面向过程而非对象。并非面向对象的形式运用不熟练(其实就是),而是这样一个程序,没有必要过度追求各种类、方法的互相联系、切换、调用之类的,建立一个“项(Term)”类,然后分配给这个类一些独有的方法与变量,然后在Main方法中大面积进行面向过程编程。体感是很顺利的一件事。(如果没有后续的第二节、第三节……)问题是在后续作业中加入新的结构与功能时,作为主体的面向过程代码则显得十分笨重。
整体思路是,将字符串录入之后直接进行格式合法性判断。此处即是我之前提到的“一万个if”。
public static Boolean checkAll (String inin) {...} public static Boolean checkPS (String inin) {...} public static Boolean checkLong (String inin) {...} public static Boolean checkNone (String inin) {...} public static Boolean checkSig (String inin) {...} public static Boolean checkRep (String inin) {...} public static Boolean checkEnd (String inin) {...}
在此声明,虽然程序简单,违法情况有限,但我并不提倡将各种不合法的情况列举。(看上去和我这个一样。)我的思路是先判断是否有非法符号,然后判断空格的位置是否合法,消去空格,寻找关键字符,判断此字符的位置是否合法,也即它和周围符号的联系是否正确。因为符号有限,所以只要每种符号自身位置没错,它与前后的联系合法,则整个字符串都是合法的。(?这不就是正则表达式文法的思想嘛??????)
合法之后,对字符串进行一定程度的格式化,使原本就不*的字符串格式更加严格,方便后面识别。(比如将加减号合并、空格消去、指数前的符号用其它字符代替)
然后将字符串根据加减号分割成若干个独立的项,每项开一个Term类的对象。(后来我才知道自己不知不觉地用了一次正则表达式。)
然后运用Term类中的求导方法对每一项求导。得到的结果仍是Term形式,将结果统一用ArrayList存储,每一项求导完毕后,若List中存在同类项则合并,否则作为新的成员存入。
最后将ArrayList中的信息统一输出。
(主要问题)
虽然运行效率,时间空间占用还可以,几百行代码量也不算复杂到让人混乱,但是……
唔,主要还是合法性判断部分吧,就算我把全部符号的关系都覆盖了,还是会有所疏漏,当时写代码时没有投入大量时间来寻找漏洞,最后让互测屋里的几个大哥帮忙指出了问题,占用了你们不少时间在此道歉,下次不要这样了。(?)
此次的漏洞在于‘^’符号,只写了它与前后字符的关系判断,而忘记写它自身位置判断,导致当输入的字符串以‘^’结尾时,自动寻找下一个(并不存在的)字符,导致爆栈出错。
另外还有一个bug,是关于空白符的判断,我在最开头用了trim函数,直接消去了所有的空白符,之后才进行合法性判断,导致遗落了当字符串中在首位存在非法空白符的情况。(明明讨论区里说了一百次了,我却没有认真看那个帖子,流下了残念的泪水。)
第二次作业
第二次作业从来源与框架的角度看,就是复用了第一次作业的代码,或者说是第一次的基础上改造而成。(但是从代码量上来看,还不如重构。)除了程序需求方面增加了一些功能之外,最大的变化是合法性判断方面,从低效复杂的“一万个if”,进化成仍然低效复杂的一万个正则表达式。
(要求概括)
跟第一次相比,增加了sin(x)和cos(x),也仅仅是他们本身,不支持其他形式的三角函数,主体仍是由几个独立的项构成的多项式,但对单独的项而言,增加了“因子”的概念,也即支持几个因子相乘构成一个项。
(个人思路)
代码结构上相对第一次十分面向过程的代码,简化了一度过于复杂的Main方法,另外构建了多项式“Poly”类,将各种诸如多项式合法性检测、格式化的操纵剥离,独立化为Poly的方法。
整体思路与上次大体相似,首先获得来自输入的字符串,先检测是否存在非法字符(这也是这次唯一的check-相对上次的七个而言。)然后通过Poly的构造方法,将字符串格式化后存为多项式类,而Poly类的存储形式为:
private int[] sigs = new int[1010];
private ArrayList<Term> termList = new ArrayList<Term>();
一个数组存着每一项的符号,另一个ArrayList以项(Term)的形式存着独立的项。这时我们来看项的存储形式:
private Boolean symbol = true;
private BigInteger coefficient = new BigInteger("1");
private BigInteger powerOfX = new BigInteger("0");
private BigInteger powerOfSin = new BigInteger("0");
private BigInteger powerOfCos = new BigInteger("0");
每一个项都必然遵循这个格式,包括符号、系数、x的指数、sin(x)的指数、cos(x)的指数五部分。然后得到每一部分的数值之后,求导就很简单了。
故而此次最棘手的地方仍是合 法 性 判 断 !
我必不可能再使用繁杂到爆炸的if!
这是什么孤儿操作?
我之前有说,
?这不就是正则表达式文法的思想嘛?????? -见第一次作业个人思路部分
是的,我此次的行为,就是把曾经用许多if实现的功能,用许多正则替换表达出来了,实质上仍然没有什么变化,都是将合法的部分消去,剩下的就是非法部分,如果为空,也即不存在非法部分,则合法。
而主流的运用正则表达式方法则是,(我也见过猪跑……)将整体概括为一个偏长的正则表达式,看输入的字符串是否符合这个格式。讲道理和我之前的手段目的相同,优劣在于,一个正则匹配高效、代码量极小,而我之前的两种手段,唯一的优势在于,猴子也能想到,但是容易出现考虑不周的情况。毕竟是猴子。
(主要问题)
仍然是两个问题。
第一个问题和第一次作业的第一个问题相同。。。上次是忘记考虑特殊符号结尾,这次是忘记特殊符号开头。:-)
虽然编程者的懒惰是一定的错误原因(第二天写了一晚上之后再也没碰)。但也一定程度上说明了,相对于其他人的一个正则表达式匹配检测,我的方法的弊端——容易出现漏洞。
第二个问题和第一次作业的第二个问题相同。。。?仍然是没有认真参与与学习讨论区的帖子。里面都清楚地总结出了三个符号同时出现的合法性,而我仍将其判断为非法。 (wsm还能让我通过中测啊,故意不在中测设置这个的吗?)
第三次作业
来了来了!我已经学会正则表达式的正确使用方法!已经没有什么好害怕的了!
然后这次的输入格式实在复杂仍然不会用一个正则表达式概括……
我回过头看见了陪伴我一路的if和正则替换……
(要求概括)
第三次的要求改变主要在于“嵌套”,包括直接括号、sin()里的嵌套、cos()里的嵌套,导致这次录入的字符串个人看来已经不能成为“多项式”,比如他可以用两个括号括起来两个多项式,互相相乘。
(个人思路)
由于懒(不是),我决定仍然复用第二次的代码,将判断合法性的方法独立为一个类,类中存在着不同的方法来判断不同格式的字符串,然后随着对源字符串的层层剥离、提取项的这个递归过程中,递归判断。
至于递归,我增加了一个TermPlus类,将和前两次作业格式相同(也即不存在括号与嵌套的部分)存为Term类,求导返回一个字符串。
不同的存为TermPlus类,然后再在TermPlus类中将最外层括号去除,对里面的内容分为三种进行计算:
♦ 简单类(可存为Term格式的),直接创建Term对象,求导,返回字符串格式的结果。
♦ 仍有嵌套(指sin、cos嵌套),但在最外层嵌套之外不存在乘号。然后返回 cos(或sin) + 原字符串 + 乘号 + 一个方法。
这个方法就是调用Main的处理初始字符串的方法,用此方法处理嵌套里面的部分,这是第一个递归过程。
♦ 存在乘号,此乘号不在任意的括号内,也即str1*str2格式。返回 “str1*递归求str2导数+递归求str1导数*str2”。
此处的递归则不再是调用Main的那个方法,而是调用TermPlus本身的本方法,也即对str1(2)再次去除外层括号,分为这三类。
最后将返回的总字符串输出。(啊,对还有格式优化什么的,明天再说吧)
(主要问题)
此次犯了一个异常睿智的错误,同时又异常xx地debug一天也没发现,导致中测最后一个点没过。
含恨宣告退出互测(明明是被宣告)。
错误本身并没有什么分析价值,故而不在此展示。(?)
最大问题出在其他方面,比如错误地估计了此次作业的难度(并没有),以为和前两次一样可以一晚上搞定(也确实一晚上写完了),第二天瞪着最后一个测试点改了一天也没过……
wsm会出现一个难以考虑到的漏洞呢?众所周知(?),出现漏洞是合法性判断环节出现了问题。
假如别人的一个正则表达式整体匹配的出现漏洞的可能系数为100。则我第二次作业的二十多个正则替换则为1000,第一次的一万个if则为10000。第三次作业同时用自然便是1000*10000。这样复杂而笨重的代码结构会出错也不足为奇了。