面向對象設計與構造第一單元 問題：表達式的化簡 表達式中僅含有$x,y,z$三種未知數 表達式僅含有$+,-,*,**,\sin,\cos,dx,dy,dx$幾種運算 - $dx,dy,dz$分別表示對$x$求導，對$y$求導，對$z$求導。 - 表示乘方，例如$23=2^3=8$ 包含若幹自定義函 ...
面向對象設計與構造第一單元
問題：表達式的化簡
- 表達式中僅含有\(x,y,z\)三種未知數
- 表達式僅含有\(+,-,*,**,\sin,\cos,dx,dy,dx\)幾種運算
- \(dx,dy,dz\)分別表示對\(x\)求導，對\(y\)求導，對\(z\)求導。
- **表示乘方，例如\(2**3=2^3=8\)- 包含若幹自定義函數。
- 化簡後的結果除必要括弧(三角函數運算符號帶的必要括弧)外不含其他括弧。
架構設計
對於表達式的問題很自然就會想到用棧去處理。
定義運算符的優先順序。
| 運算符 | 優先順序 |
|---|---|
| ) | 0 |
| +、- | 1 |
| * | 2 |
| ** | 3 |
| ( | 4 |
首先考慮如果表達式中不含字母只含數字應該如何計算。考慮雙棧結構按照如下流程處理
(這裡僅討論主體架構，關於細節方面就不再贅述)。
flowchart LR node_1["讀取"] node_2{"判斷"} node_3["壓入數字棧"] node_4["壓入符號棧"] node_5{"優先順序#lt;=符\n號棧頂元素"} node_6["數字棧pop\n數字棧pop\n符號棧pop"] node_9["將出棧的三個元\n素進行運算並將\n結果壓入數字棧"] node_11{"符號棧空?"} node_7{"符號棧頂為(？"} node_8{"當前符號為)?"} node_10["符號棧pop"] node_1 --> node_2 node_2 --"數字"--> node_3 node_3 --> node_1 node_2 --"運算符"--> node_5 node_5 --"NO"--> node_4 node_4 --> node_1 node_5 --"YES"--> node_11 node_11 --"YES"--> node_4 node_6 --> node_9 node_9 --> node_5 node_7 --"NO"--> node_6 node_11 --"NO"--> node_7 node_7 --"YES"--> node_8 node_8 --"NO"--> node_4 node_8 --"YES"--> node_10 node_10 --> node_1對於求導運算與三角函數運算，他們都是單元運算，並且運算作用範圍必有一對()，
因此當符號棧頂為求導運算和三角函數時直接取出計算即可。
PS:有關自定義函數的處理，我採用了一種比較簡單直接的辦法——字元串替換。即把實參截取出來將函數表達式中的形參替換掉。
我們仔細思考用棧計算表達式的流程，容易發現其只關心表達式的運算結果而並不關心表達式的層次結構。
所以後續的作業關鍵點就轉換成瞭如何用合理的數據結構表示運算結果。
第一次作業當中不含三角函數、自定義函數以及求導，因此輸出結果僅表現為若幹單項式的和。
於是用單項式組合成多項式的結構並定義單項式類及多項式類的加法乘法就能很輕鬆的解決。
第二、三次作業引入了三角函數，上述結構便不再適用了。
引入三角函數之後的難點在於三角函數之間的相互嵌套。這種互相嵌套的結構類似於樹結構，於是我們考慮用類似表達式樹的結構表示運算結果。
每個樹結點記錄兩個信息：
- 此結點所表示子樹的運算結果外是否需要再加上一個三角函數運算。
- 此結點的所有兒子結點之間的運算關係。(葉子結點忽略)
對於葉子結點只需記錄此結點對應的多項式(即將第一次作業的設計封裝進去)
例如樹
flowchart TB node_1(("null\n+")) node_2(("sin\n+")) node_3(("cos\n*")) node_4(("x<sup>2</sup>*y")) node_5(("z")) node_6(("x*z")) node_7(("y")) node_8(("x<sup>4</sup>")) node_1 --- node_2 node_1 --- node_3 node_2 --- node_4 node_2 --- node_5 node_3 --- node_6 node_3 --- node_7 node_3 --- node_8即表示表達式\(\sin(x^2*y+z)+\cos(x^4*x*z*y)\)
接下來只需要定義兩棵樹之間的加法和乘法。
兩棵樹的加法：
flowchart TD node_1[/"a"\] node_2[/"b"\] node_3(("null\n+")) node_4[/"a"\] node_5[/"b"\] node_3 --> node_4 node_3 --> node_5兩棵樹a,b的乘法：
- 如果其中一棵樹a根結點具有"null +"的形式，則新建一個根結點\(root\)，將a根結點的每個子結點與b做乘法的結果作為\(root\)兒子結點。\(root\)所代表的樹就是運算結果。
- 如果兩棵樹都具有"null +"形式，則需要將a,b根結點的子結點兩兩相乘。
- 如果都不具有"null +"形式，則簡單模仿樹的加法進行處理即可。
- 葉子結點需要特殊處理，調用第一次作業當中寫好的多項式乘法即可。
當然僅僅只做好樹的乘法和加法是不夠的，因為這還無法實現化簡的目的。為此，我們還需要做以下約定：
- 對於具有"null +"形式的結點，若其只有一個兒子，則用兒子替代這個結點。
- 對於具有"null *"形式的結點，不允許其兒子中出現"null +"。
加入求導因數後，只需按照求導法則為樹建立求導方法即可。
合併同類項(樹哈希)
- 一般合併同類項有兩種思路
- 逐字元的比較判定。
- 為每個表達式建立哈希值。
- 但是前者操作比較繁瑣且時間複雜度較高，後者如果沒有較好的衝突處理機制則很容易被hack。
- 逐字元比較複雜度高的原因就是有大量的重覆比較，我們考慮如何減少這種重覆比較。
- 由於這次作業我是用樹構建的，下麵介紹一種關於樹的哈希方法，值得一提的是這種哈希方法不會產生衝突。
為了簡單起見，下麵以一棵普通的無根樹為例
flowchart TB node_1((" ")) node_2((" ")) node_3((" ")) node_4((" ")) node_5((" ")) node_6((" ")) node_7((" ")) node_8((" ")) node_9((" ")) node_10((" ")) node_11((" ")) node_1 --> node_2 node_1 --> node_3 node_1 --> node_4 node_2 --> node_5 node_2 --> node_6 node_3 --> node_7 node_4 --> node_8 node_4 --> node_9 node_9 --> node_10 node_9 --> node_11從葉子結點開始，我們給每個特定的結構一個唯一的編號。
flowchart TB node_1((" ")) node_2((" ")) node_3((" ")) node_4((" ")) node_5(("1")) node_6(("1")) node_7(("1")) node_8(("1")) node_9((" ")) node_10(("1")) node_11(("1")) node_1 --> node_2 node_1 --> node_3 node_1 --> node_4 node_2 --> node_5 node_2 --> node_6 node_3 --> node_7 node_4 --> node_8 node_4 --> node_9 node_9 --> node_10 node_9 --> node_11往上一層出現了兩種新的結構，
flowchart TB node_1((" ")) node_2(("1")) node_3(("1")) node_4((" ")) node_5(("1")) node_1 --> node_2 node_1 --> node_3 node_4 --> node_5我們給他們標號為2，3
flowchart TB node_1((" ")) node_2(("2")) node_3(("3")) node_4((" ")) node_5(("1")) node_6(("1")) node_7(("1")) node_8(("1")) node_9(("2")) node_10(("1")) node_11(("1")) node_1 --> node_2 node_1 --> node_3 node_1 --> node_4 node_2 --> node_5 node_2 --> node_6 node_3 --> node_7 node_4 --> node_8 node_4 --> node_9 node_9 --> node_10 node_9 --> node_11又出現了新的結構
flowchart TB node_1((" ")) node_2(("1")) node_3(("2")) node_1 --> node_2 node_1 --> node_3編號為4
flowchart TB node_1((" ")) node_2(("2")) node_3(("3")) node_4(("4")) node_5(("1")) node_6(("1")) node_7(("1")) node_8(("1")) node_9(("2")) node_10(("1")) node_11(("1")) node_1 --> node_2 node_1 --> node_3 node_1 --> node_4 node_2 --> node_5 node_2 --> node_6 node_3 --> node_7 node_4 --> node_8 node_4 --> node_9 node_9 --> node_10 node_9 --> node_11最後給結構
flowchart TB node_1((" ")) node_2(("2")) node_3(("3")) node_4(("4")) node_1 --> node_2 node_1 --> node_3 node_1 --> node_4編號為5
flowchart TB node_1(("5")) node_2(("2")) node_3(("3")) node_4(("4")) node_5(("1")) node_6(("1")) node_7(("1")) node_8(("1")) node_9(("2")) node_10(("1")) node_11(("1")) node_1 --> node_2 node_1 --> node_3 node_1 --> node_4 node_2 --> node_5 node_2 --> node_6 node_3 --> node_7 node_4 --> node_8 node_4 --> node_9 node_9 --> node_10 node_9 --> node_11至此，所有不同的樹結構都有了一個獨一無二的編號，我們就可以很方便的依據這個編號合併同類項了。
但是本人並沒有在作業中實踐這個樹哈希，只是口胡了一下，感覺為了這點性能分不是很有必要，也沒有什麼意思，遂潤去cf、atc玩耍。
PS:此方法也可以用來判定兩棵無根樹同構，方法是找到兩棵樹的重心並以重心為根進行樹哈希（由於樹可能有兩個重心，所以最壞情況下要做四次。）
bug分析
- 這輪作業基本沒什麼bug，第一次作業被hack了一下，是理解錯題意了，以為字母前面也可以帶一個符號。
- 第三次作業強測WA了一個點是因為新增的求導方法寫的比較快，忘記滿足上面說的第二條約定了。
重構
- 這三次作業我並沒有任何的重構，都是不斷增量開發直至最終成形。
互測
- 我沒有特意閱讀別人代碼去刀人，感覺之前在codeforces和UOJ上都快玩膩了，就不是很有興趣，就是無聊的時候隨手交幾個比較簡單的數據玩玩，但沒想到還真刀中了一個，我記得那個數據是sin(sin(0)**0)答案應該是sin(1)但那個xd輸出了0，估計是捲性能分反而捲錯了(樂)。
一些想法
作為沒有選先導課，寒假又完全沒有預習的人（其實寒假買了大黑書的，但直到開學它都還是嶄新的bushi）剛開始對於不會java還是有點慌的，但是好在編程語言之間的本質都是相通的，我對C/C++也比較熟悉，於是看了1個多小時java語法遂上手開始寫代碼。
於是就出現了辛辛苦苦寫完了一個方法，卻被告知是java庫里自帶的。。。(卒)
很奇怪的一點，作業開始之前所有人都告訴我不要用棧去寫，根本寫不出來。但是實際上我寫下來並沒有感覺到什麼阻力，而且用棧寫考慮的重點就只有多項式的乘法加法，第二次作業就變成樹的乘法加法，第三次作業就加個樹的求導。這樣的思路不是應該比什麼遞歸下降又是term又是factor又是expr的設計更自然更簡單嘛。
還有一種說法是棧並不能體現表達式的層次結構，我覺得也不盡然，棧並非不體現層次結構，而是把層次結構表現在計算結果中了。
因此，我並不覺得表達式求值適合作為面向對象的作業，我覺得一切架構的設計都是為了讓問題變得簡單，使問的本質更加清晰。
而表達式求值的本質已經足夠簡單清晰了，再去拼命想所謂精妙架構反而會使問題複雜化。建萬丈高樓需要穩固的腳手架，但是搭玩具積木再這麼做就完全沒有必要。
不管是面向過程、面向對象還是面向函數，任何編程模式的設定都是為了簡化問題，解決問題就是要回歸到問題本身具體問題具體分析，把表達式作為課程的作業就有為了面向對象而面向對象之嫌。
華羅庚說過數學就是要足夠的退退到原始而又不失本質的地方，我覺得程式設計也是如此，既然棧--樹的設計已經觸及到了問題的本質，那就不必反其道而行之。
說實話，對於本人來說，這次作業寫下來著實有些無聊，題目也顯得過於稀鬆平常，略有挑戰的地方在於代碼規模，以前寫過最長的代碼就是200行左右的Link-cut-tree、動態DP、樹套樹之類的玩意。這次作業總代碼量已經有800+行，但寫完之後完全沒有寫出上述演算法之後的喜悅感和成就感，感覺只是完成了課程的一個任務罷了。
另外，年年表達式、年年電梯，難道不膩嗎，是不是該換換題了呢？
