目錄
- 一、程式結構分析
- 第一次作業
- 第二次作業
- 第三次作業
- 二、Test & Bugs
- 三、設計模式
- 四、總結與反思
思路：
1.輸入預處理：
- 去除空格和\t
- 替換++、--、+-、-+
- 将+x，-x，x+，x-替換成+1*x，-1*x，x**1+，x**1-。至此已将輸入中的每一項全部替換成[+-]\d+*x**[+-]?\d+
- 最後用正則提取每一項
2.合并化簡求導
HashMap<BigInteger, BigInteger>存儲用正則提取的項的系數，指數，邊提取，邊比較，邊化簡
3.關于格式化輸出
因為系數和指數都是整數，是以求導之後隻有指數是-2的項需要考慮系數是否為1或-1
求導之後指數是0，直接輸出系數；指數是1，如果系數還是1或-1，那麼求導之前項的系數隻能是分數，如果隻按指數讨論，筆者的格式化輸出邏輯減少5-6行，當然你也可以像第一次實驗的輸出要求一樣讨論
UML:
LinesCounter:第一次代碼總行數128
Metrics:第一次作業尚未飄紅
1.判斷表達式合法
- 判斷是否為空串
- 以項為機關構造正則，逐項比對
2.合并因子并求導：
建構求導的抽象類，每種函數繼承抽象類，友善合并因子及求導
3.化簡：
合并同類項：
對于x，sin，cos的指數相同的兩項，合并系數：重寫了
hashcode
和
equal
方法，把x,sin,cos的指數當成三元組，把三元組當成
Hashmap
的
key
，系數當成
Hashmap
value
，通過判斷是否
containkey
，進行同類項的合并
分類：
按照x的指數分類，将系數，sin的指數，cos的指數當成三元組
對于指數不同的項無需考慮三角函數的化簡
對于每個x的指數對應的若幹三元組深搜剪枝化簡：
設sin指數為m，cos指數為n，則對于①(m,n) ②(m,n+2) ③(m+2,n)
①②③任選兩者的組合都可以轉換成另選兩組的組合。為友善讨論，設兩項的公共部分為F，詳細讨論如下：
①+② <--> ①+③：a*F+b*F*cos(x)**2 <--> (a+b)*F-b*F*sin(x)**2
②+③ <--> ①+②：a*F*sin(x)**2+b*F*cos(x)**2 <--> a*F+(b-a)*F*cos(x)**2
①+③ <--> ②+③：a*F*sin(x)**2+b*F <--> (a+b)*F*sin(x)**2+b*F*cos(x)**2
類似轉換方式還有：
a*F*cos(x)**2+b*F <--> -a*F*sin(x)**2+(a+b)*F
a*F*cos(x)**2+b*F*sin(x)**2 <--> a*F+(b-a)*F*sin(x)**2
a*F+b*F*sin(x)**2 <--> a*F*cos(x)**2+(a+b)*F*sin(x)**2
利用可能使結果長度縮短的以上轉換，進行深搜剪枝化簡
深搜：
标記+回溯，對于每個沒有被通路的三元組，嘗試按照6種轉化形式變換，遞歸到底之後判斷總長度是否減小
剪枝：
采用貪心的思想，每次轉換同時将轉換之前的項設定成對照，如果未能使長度減小，直接
return
熔斷：
根據第二次評測機2s限定的CPU時間，設定深搜部分的時間門檻值1000ms，即超過1000ms之後直接throw exception
4.格式化輸出：
重寫toString
類之間的邏輯和調用關系：
LinesCounter:第二次代碼總行數733
Metrics：化簡部分的複雜度較高
1.判斷表達式合法：
- 排除空串(隻有空格和\t的也算作空串)
- 排除非法字元
- 排除空格引發WF的情況
- 排除非法階乘
- 排除非法三角函數
- 排除非法數字
- 去掉空格和制表符
- 排除非法加法減法符号
- 排除非法指數和底數
- 排除不比對的括号
2.求導：
隻對表達式因子和嵌套類的三角函數建樹處理，其餘正常處理。建樹時按照優先級嵌套>乘法>加法=減法，設定權重，友善建樹
求導結果隻有*,+,-，是以遞歸化簡，去除多餘的0，1，括号
LinesCounter:第三次作業總行數1508
Metrics：由于循環和判斷邏輯較多，是以大面積飄紅
Test:
在第一次作業強測之前已搭建好評測機，三次作業使用隻需改變生成資料的正則
- 1.用xeger根據自己設計的正規表達式批量生成測試資料的檔案input.txt
- 2.然後将input.txt逐行作為輸入 ,運作.class 獲得輸出檔案tmpOutput.txt
- 3.然後對tmpOutput.txt的内容采用sympy進行表達式求值(比如代入x=2),獲得輸出檔案myOutput.txt
- 4.用sympy包對input.txt的内容逐行求導并進行表達式求值,令x=2,獲得輸出檔案correctOutput.txt
- 5.比較myOutput.txt和correctOutput.txt,如果存在不同,根據行數查找input.txt的測試資料
按照1-5的邏輯編寫.sh ，bash運作完成黑盒測試
具體細節處理：
1.1去除生成資料的前導0
#去除前導0
str = re.sub(r'(?<!\d)0+(?=\d)', "", str)
1.2 代入2計算
result = int(expr.evalf(subs={x: 2}))
1.3 使用管道，簡化sh編寫
cat $InputFileName | while read line
do
...
correctOutput=$(echo "$line" | python diff.py)
result=$(echo "$myOutPut$space$correctOutput" | python compare.py)
...
done
另一種測試方法：Junit
//本次主要使用sh
import org.junit.Test;
import JUnitTestTools.EnhancedUserTestTools;
import java.io.File;
public class PolyTest {
@Test
public void main() throws Exception {
new EnhancedUserTestTools(Poly.class, 2000).testAll(new File("./test/poly/test1.txt"));
}
}
Bugs
強測：
三次強測均未測出bug
hacked:
三次互測均未被hack
hack:
三次互測平均每次hack非同質bug2個，其中主要是輸出時toString的邏輯和細節處理，以及第三次作業存在的優化過度的問題。
主要采用工廠模式。
第一次作業由于僅用128行實作，沒有考慮向後相容性，是以沒有設計工廠（之後單元應該着重注意代碼向後相容的能力）
第二次作業考慮了向後相容性，設計了抽象類，sin,cos,pow,const均繼承抽象類，搭建工廠
第三次作業在第二次作業的基礎上，實作遞歸邏輯。配合樹結構的使用，保證了正确性
三次作業主要鍛煉了各個容器的使用，工廠模式的應用，優化方式的探索。雖然三次作業的完成都保證了正确性，但尚有很多不足。比如第三次作業中采用二叉樹的結構，①是給後續的化簡帶來極大的困難，②是樹結構與業務邏輯緊密綁定，可能無法滿足後續的擴充要求。但是如果設計一個統一的item接口，然後不僅讓sin,cos,pow,const實作這個接口，而且讓各個組合項+,-,*,嵌套也實作這個接口，隻需要組合項是内置兩個item一個operator，不僅友善化簡，而且無需采用樹結構，簡化代碼邏輯，同時能保證向後相容性，無論之後出現新的因子，還是新的組合模式，隻要執行個體接口即可。
相比于正确實作功能，個人認為優化部分更具有挑戰性，尤其是在優化的同時，保證正确性，而不是因為20分失去應得的80分。比如在第二次作業中，采用了dfs深搜的優化方式，但可能會出現TLE的問題，是以要設定熔斷。在第三次作業中，如果采用二叉樹，可能面臨無從化簡的處境。