第一次作業
1.項目結構
本次類主要分為3個，main類，用于預處理的Preprocess類和用于拆解，求導并列印表達式的PowFunc類。
第一次的作業比較簡單，不需要判斷Wrong Format，隻需要将表達式預處理成友善求導的形式然後求導就可以了。預處理過程主要分為以下幾步：
1.去除空格
2.将多個連續的正負号變為一個
3.補充缺失的系數（+1，-1等）
4.補充缺失的指數**1。
2.代碼複雜度分析
由上圖可以發現方法的複雜度整體都不高，但是printterm函數的複雜度明顯很高。導緻printterm複雜度升高的部分如下圖所示：
圈複雜度大說明程式代碼可能品質低且難于測試和維護。确實在寫這塊代碼課下自己測試的時候這裡發現了不少問題。這也啟示了我以後寫完代碼後可以用代碼複雜度分析工具分析子產品的複雜性，針對複雜的子產品要多設立測試點測試。根據帕累托原則，20%的子產品中可能含有系統80%的bug，是以測得bug的子產品往往含有更多的bug，需要多加測試。
3.bug分析
（1）合并同類項
第一次作業中我在合并同類項的時候出現了bug，因為我根據每一項建立了一個HashMap，Key為指數，Value為系數。由于我在合并同類項時簡單地讓HashMap判斷是否contains Key的字元串，然而這導緻了一個嚴重的問題就是形如指數為“2”和“+002”的兩項并不會被合并，因為它們字元串并不相同，然而實際上指數是相等的。是以一個方法是先把指數轉為BigInteger再比較，這樣的話由于BigInterger相容性較好，可以自動把“+0002”這種既帶正負号又帶前導0的數字轉化為标準格式。之後比較字元串時就不會出現這種問題。
（2）一些特殊的情況
比如-x+x，因為有的同學優化時項為0的不輸出是以最後的結果是沒有輸出，導緻bug。
（3）map中周遊時删除操作的正确方法
for (Iterator<Map.Entry<String,String>> it = map.entrySet().iterator(); it.hasNext();) {
Map.Entry<String,String> item = it.next();
String cofficient = item.getValue();
if (cofficient.equals("0")) {
it.remove();
}
}
而以下兩種Map的周遊方法都不适合做删除操作：
HashMap<String,String> map = new HashMap<>();
Set<String> key = map.keySet();
for (String s : key) {
//do something
map.remove(s);
} HashMap<String,String> map1 = new HashMap<>();
Set<Map.Entry<String,String>> entrySet = map1.entrySet();
for(Map.Entry<String,String> entry : entrySet) {
//do something
map1.remove(entry.getKey());
} 第一次作業中互測時有同學采用了不正确的周遊方法删除之後就會出現bug。
（4）正規表達式使用注意事項
- 正規表達式不宜寫的很長，如果寫的比較則應該分成多條來寫，增強代碼可讀性同時友善自己debug,正規表達式debug的方法可采用下文中的第（5）條，使用check RegExp來檢查。
有的同學正規表達式隻寫成了一條，寫的很長，就很容易出bug，互測當中我看到了這樣寫的同學就去測他的正規表達式，果然發現了bug。
- 前2次作業中由于沒有空白引起的Wrong Format，是以我把所有空格去掉後再比對格式，這樣就可以适當縮減正規表達式的長度降低出錯幾率。
- 正規表達式需要留神爆棧問題。雖然在我們這屆的指導書中往往對輸入字元串的長度有較強的限制一般不容易出現爆棧的現象，然而在往屆同學的部落格中提到确實存在有的同學在互測中由于正規表達式爆棧而出錯的情況。
- 為了防止正規表達式爆棧，可以采取以下政策：
- 懶惰比對
- 了解自動機原理後做原理層面的優化（很複雜）
（5）小技巧1：BigInteger中自帶的固定值
BigInteger中有三個基本常理：
BigInteger.ZERO
BigInteger.ONE
BigInteger.TEN -1
可以采用
BigInteger.ONE.negate()
以指派。
（6）使用intellij自帶的check RegExp來友善地檢測正規表達式是否正确。
在正規表達式“”中的任意一處點選一下，就可以在左側的下拉菜單中選取check RegExp選項，然後可以在彈出框中輸入字元串，會顯示字元串是否比對正規表達式。
字元串如果比對則如下圖所示：
字元串如果不比對則如下圖所示：
第二次作業
第二次作業引入一個新子產品Wrong，主要用來判斷是否Wrong Format。由于第二次作業正規表達式不會出現嵌套的現象，故根據指導書寫出所有的正規表達式便可輕松地判斷表達式是否符合格式。
2.代碼複雜度分析
由上圖可知，derive子產品的複制程度較高，應繼續做類的拆分。derive子產品核心代碼如下：
if (coff.compareTo(bigZero) == 0) {
continue;
} else {
for (int i = 0;i <= 2;i++) {
System.arraycopy(indexArr,0,indexArrNew,0,3);
if (indexArr[i].compareTo(bigZero) == 0) {
continue;
} else if (i == 0) {
coffNew = indexArr[i].multiply(coff);
indexArrNew[i] = indexArr[i].subtract(bigOne);
} else if (i == 1) {
coffNew = indexArr[i].multiply(coff);
indexArrNew[i] = indexArr[i].subtract(bigOne);
indexArrNew[2] = indexArr[2].add(bigOne);
} else if (i == 2) {
coffNew = indexArr[i].multiply(coff).multiply(bigNegOne);
indexArrNew[i] = indexArr[i].subtract(bigOne);
indexArrNew[1] = indexArr[1].add(bigOne);
}
//放入map
System.arraycopy(indexArrNew,0,indexArrNewPut[bigArri],0,3);
if (mapRet.containsKey(indexArrNewPut[bigArri])) {
mapRet.put(indexArrNewPut[bigArri],
mapRet.get(indexArrNewPut[bigArri]).add(coffNew));
} else {
mapRet.put(indexArrNewPut[bigArri],coffNew);
}
bigArri += 1;
}
這裡可以采用工廠模式，建立一個求導後項的系數和指數的值的工廠。傳入原系數和指數數組的HashMap和循環變量i，傳回求導之後各項組成的HashMap。這樣就可以大大降低derive子產品的複雜度，可讀性更強。
（1）帶有前導0的指數求導依然是易錯點
本次我在公測和互測中都未被hack，hack了别人的兩個bug：
-+x*x**2*x**+00002*-4*sin(x)*sin(x)**2*sin(x)**-0002 x*sin(x)**0002*sin(x)**-0001*sin(x)**-1 這說明在第二次作業中帶有前導0的複雜指數化簡依然是一個容易出錯的問題。
下面我想說一個在課下讓我“命懸一線”的問題
（2）非常不建議把數組類型作為HashMap的Key。
在做第二次作業時在求導方面我并沒有考慮很好的擴充性，考慮了一種“投機取巧”的辦法，即所有的項都有一個通用的形式a*x**b*sin(x)**c*cos(x)**d，每一項求導之前與求導之後的格式都為a*x**b*sin(x)**c*cos(x)**d。是以我建了一個存儲項的HashMap，Key為int[3]的數組，分别存儲x,sin(x)和cos(x)的指數，即[b,c,d]，Value為前面的系數，即為a。我最初的想法是這樣建的話有利于合并同類項，因為不能合并同類項的兩項之間[b1,c1,d1]和[b2,c2,d2]并不相同。
然而當我使用map.contains(int[])的時候卻發現并沒有像我想的那樣成功合并同類項。原因在與map.contains()比較兩個Key的時候的原理是采用.equals()方法，然而這個方法并不能比較兩個含有相同值的數組，是以map.contains()無法通過正常的方法來識别是否含有一樣的數組。如下方的代碼會輸出false:
int [] a = {1,2};
int [] b = {1,2};
boolean c=a.equals(b);
System.out.println(c); 第三次作業
1.項目結構
（1）判斷格式的非遞歸實作
- 指導書上給的正規表達式會需要遞歸調用，然而java的正規表達式并不能像有的語言一樣可以遞歸調用（不知道為什麼不加這個功能）
- 下圖即為指導書中有關遞歸調用正規表達式的過程
- 經過仔細思考可以換一種非遞歸了解方式，即因子可以帶括号（也就成了表達式因子），也可以不帶（其他因子）。
- 項可以是一個因子，表達式也可以是一個因子。
- 是以項兩側可有括号可沒有，表達式也是如此。
- 故代碼可如下所示：
private static String factor = "(" + func + "|" + integer + ")";
private static String item = "(\\(?(" + plusOrMinus + tab + ")?" + factor + tab
+ "(\\*" + tab + factor + ")*\\)?)";
private static String poly = "\\(?" + tab + "(" + plusOrMinus + tab + ")?" + item + tab+ "([+-]" + tab + item + tab + ")*" + "\\)?"; 經測應該無誤，通過了所有自己和公測的Wrong Format測試點 。
- 之後判斷指數大小是否符合範圍
- 通過棧判斷表達式的括号是否比對（有的同學沒有考慮）
（2）求導過程的非遞歸實作
其中我想重點講一下我的求導方面的架構設計。讨論區中以及絕大部分人的方法基本都離不開遞歸，或者建構了表達式樹然後再遞歸。然而這樣導緻一個問題就是遞歸層數如果深的話就有可能導緻爆棧，如：
((((((((((((((((((((((((x)))))))))))))))))))))))))))。是以你讨論區裡很多同學提出可以拆除沒有意義的括号，我想到的情形主要有以下幾種：
- ((((((((((((((((((((((((x)))))))))))))))))))))))))))，因子兩邊嵌套數層括号但其實并沒有什麼意義，故如果兩層括号緊密相連，如(())，就可以拆除其中的一層括号。
- (x+(x+(x+……，括号外側由正号或者負号連接配接，括号無用，可直接去除。
- (x*(x*(x+……，雖然括号外側由乘号連接配接，但是括号内部是一項，即沒有項與項之間的正負号，則括号無用，可以直接去除。
然而有一些項是不能通過這種方式來去除括号的，比如sin(sin(sin……sin(x)……），最多可以有11層。雖然資料限制或許導緻并不會爆棧，然而這個問題并沒有得到真正解決，即遞歸層數稍一變多就會爆棧。
是以我覺得采取一種非遞歸的算法，雖然思考難度比遞歸大不少但是可以一勞永逸地解決問題。遞歸其實是從最外層的括号開始求導，如果内層函數含有括号則繼續遞歸。而非遞歸方法則與之相反，先求出最内層括号的導數值，然後一層一層向外求導。這個題目可以采取非遞歸的算法的本質原因是你可以根據表達式預知括号的層數即分布。也就是說根據表達式可以先建立一個字元數組，将表達式中所有的括号放入其中。然後就可以得知括号的層數，之後就可以先把最内層的一個或多個括号内的表達式求出導數，同理向外求導直到沒有括号。由于我在執行此方法時會在整個表達式外套上一層括号，故求到最外層後即為整個表達式的導數。這個方法聽起來并不困難，但其實寫起代碼來卻要解決好幾個遞歸不需要考慮的問題，難度較大。
下面舉一個簡單的例子解釋這個方法。比如對這個表達式進行求導：(x+1)*(x+2)，
- 第一步給外層加上括号((x+1)*(x+2))
- 第二步提取括号數組：(()())，易得括号深度為2。
- 第三步求出所有深度為2的括号内的表達式的導數，都為1.
- 第四步求出最外層括号内對應表達式中的導數。
以上6個方法為第三次作業中是以複雜度不符合規範的方法。前兩次作業分别隻有1個和2個方法不符合規範，充分說明了在方法劃分不合理的時候，當一個工程的代碼變複雜以後，複雜的子產品數目幾乎以指數的速度增長，複雜的子產品也導緻出bug的機率大大增加。
其中第一張圖中的四個方法全部與求導有關，這四個方法的含義分别是給因子進行求導，給一項進行求導，和對整個表達式進行求導。z這幾個方法中由于使用了嵌套的if-else使得複雜度一下升高，故可以采用的工廠模式的方法，工廠生産幂函數，sin函數，cos函數的導數，然後求導方法裡直接調用可以很好地降低方法的複雜度。
（1）括号不比對
有的同學并沒考慮到括号不比對導緻WRONG FORMAT的問題。判斷括号比對最好的方法之一是使用棧，遇到一個左括号就入棧，遇到一個右括号就出棧一個左括号。如果最後棧中括号的數目為0就說嘛括号比對。
（2）輸出格式錯誤
比如輸出（表達式）**0這種答案，可行的方法是使用正規表達式将這種式子替換為1。
（3）遞歸爆棧
有的同學遞歸沒有做任何預處理，導緻((((((((((((((((((((((((x)))))))))))))))))))))))))))這種遞歸深度很深的表達式直接爆棧。
應用工廠模式重構
我覺得針對我的代碼接口主要可以改為3個，預處理，求導和簡化。這三步主要操作都可以分為好幾部小操作，可以使用工廠模式進行實作。
在重構時應主要參考前文中子產品的複雜度，對含有嵌套的大量if-else子產品以及行數大于要求（最好不超過30行）的子產品進行拆解或者使用工廠模式，比如第三次作業中的幾個求導子產品，都出現了if-else嵌套導緻複雜度迅速上升的現象，可以用工廠模式進行解決。
具體到因子的求導還可以使用求導因子的接口，分别用幂函數，sin函數，cos函數求導的方法進行實作。
分析别人bug的政策
- 首先可以采用“盲測”的方法，即輸入自己覺得易錯的測試點，不管對方的代碼結構，這種方法雖然暴力但很多時候卻很有效。
- 如果遇到對方寫很複雜的正規表達式則可以測試對方的正規表達式是否正确，是否會出現爆棧等現象。
- 遇到對方有比較明顯的結構錯誤，如hashmap周遊删除元素時采用了不穩定的方法，那麼就多多構造需要删除元素的資料點，很容易就測得對方的錯。
- 我覺得除非對方有明顯的結構錯誤或者不規範的地方，否則單純看對方代碼可能很難發現bug，這是采取暴力對拍可能能更快地發現bug。
- 對拍隻能作為手動測試的補充，因為對拍生成的資料點随機性較強但是不一定很強，有同學反應在互測過沉中評測機對拍未發現任何bug，而手測反而發現了好幾個bug。
對比和心得體會
1.關于性能優化
- 保證正确性是最重要的，如果有的優化性能使程式具有很高的複雜度那麼就應該放棄對應部分優化。比如第三次作業中如果細究所有的優化可以說是無窮無盡的，三角函數嵌套的表達式具體的化簡甚至有專門的論文，而完全把時間全部放在優化上其實并不劃算而且風險不小。我記得讨論區裡有人說過有的大佬優化的結果比simplify還要簡單,說明即使是工業級的函數也追求的是在不太多的函數内盡量達到最好的效果，而非必須追求數學上的極緻完美，如何學長在優化時采用了蒙特卡洛的方法，雖然在數學上不一定能化簡到完美，卻可以用不是很複雜的代碼達到較好的效果，在應用中更具有實用性。而在性能分數中事實證明隻要做到一些很基本的優化：包括合并同類項，去除0項，省略系數和指數，就可以取得很好的性能成績。
2.關于類的拆分
- 應适當增加類的數目，使得每個類都不很複雜，如田佬和林佬等的代碼中都有很多個類，每個類往往不太複雜。
- 單個方法控制最長不超過30行左右，單個類的長度盡量控制在100行左右。如果超過這個長度，就要考慮将其進行細分。
- 包（Package的使用）：設立很多個類後還可以把類根據類别放在不同的package中，使類看起來比較整齊不雜亂，同時不同包裡的方法還可以采用相同的名字，這樣就不用擔心名字重複的問題。而我在前3次作業中簡單粗暴地把所有問你件放在src裡，結構并不清晰明了。
- 包的詳細應用方法可參考以下資料：https://www.runoob.com/java/java-package.html
- 田佬對方法的拆分就很細緻，感覺很“面向對象”，值得學習。
3.測試資料
- 自動化評測機可以節約大量測試的時間，然而對拍隻能作為手動測試的補充，因為對拍生成的資料點随機性較強但是不一定很強，有同學反應在互測過沉中評測機對拍未發現任何bug，而手測反而發現了好幾個bug。這也引來了一個問題，如何有政策地生成資料達到強測的效果。其實我在計組的時候也體會到了這一點，真正随機生成的資料其實很弱，很多bug都測不出來，這時就要有政策地生成強測資料。比如我覺得在前3次作業中大部分特殊情況都與0,1，-1這幾個數字有關，無論是省略還是化簡部分。為了普遍性，再加入2，-2這兩個值，因為在數學上可以近似認為如果2和-2都對那麼3和-3以及其他不是0,1，-1的數字就很可能也對。是以就可以讓表達式的系數和指數都限定在0,1，-1，2，-2範圍内随機生成資料自動比對。
4.常見集合類型用法的簡要總結
- ArrayList：底層基于數組，在java中自認為基本可以代替數組使用，查詢快，增删慢，線程不安全。
- LinkedList：底層基于連結清單，查詢慢增删快，線程不安全。
- set集合相同的元素隻能含有一個，有時候當需要保證相同的值隻能保留一個的使用場景中很有用。比如寒假作業就有一道這樣的題。
- HashSet:無序，存儲順序和取出順序不一緻。
- LinkedHashSet：存儲和取出順序一緻。
- TreeSet:使用自然順序進行排序，或者按照建立treeset時建立的Comparater排序。
- HashTable：Key和Value都不允許出現Null值。
- HashMap：随着時間的推移Map中的次序可能發生改變，NUll可以作為鍵。HashMap不推薦Key類型使用數組，詳情請見本文第二次作業的bug分析。
- TreeMap：根據Key對節點進行排序。
5.帕累托定律
- 20%的子產品會承擔程式80%的功能
- 20%的子產品往往會出現程式80%的bug
- 容易出bug的20%的子產品往往是最複雜的子產品，故修改bug的同時也有可能引來新的bug。有研究表明，20%以上的場景中當修複複雜子產品的bug時，會引入新的bug
- 啟示：可以分開簡單地測試一下各個子產品，對測出bug的子產品必須反複測試。同時為了防止修複bug的時候引入了新的bug，修複bug 的過程需要滿足回歸測試，即之前運作正确的資料點必須依然運作正确。Junit可以比較友善地進行回歸測試，子產品測試。我第一單元作業還沒用過，以後盡量嘗試使用。
6.構思清楚再寫代碼
- 把思路甚至是比較具體的細節構思清楚之後再開始敲代碼，不要急于敲代碼。上學期高老師曾說過，設計代碼時期耗費的時間會加倍地報答你。見過有的同學想構造表達式樹但在敲代碼前并沒有構思清楚，導緻寫了一半之後覺得寫不下去了出現很多bug直接重構，耽誤了大量時間。
7.雜七雜八
- 不要把事情拖到DDL，因為OO工作量大，拖到DDL是真的寫不完，也見過很多同學奮鬥到最後一小時（我也是其中之一）。
- 适當增加一些處理異常的語句，如try catch等，雖然對通過資料點貌似沒有直接幫助，然而讓自己的程式面臨難以預測的各類異常時盡量不會崩潰确是軟體的重要職能之一。
- 我的代碼雖然也使用了一些面向對象的思想，然而還是挺不“面向對象的”，類的拆分方法的拆分不盡合理，java的現成輪子用的也不到位，在作業中為了短時間内追求正确性也沒有用工廠模式來寫，同時異常處理什麼的也沒有做，可以說缺陷确實特别多，同時分數也比較不理想，希望我第二單元可以做的更好。