面向物件設計與構造第一單元
問題：運算式的化簡
- 運算式中僅含有\(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+行，但寫完之后完全沒有寫出上述演算法之后的喜悅感和成就感，感覺只是完成了課程的一個任務罷了，
另外，年年運算式、年年電梯，難道不膩嗎，是不是該換換題了呢？
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/547120.html
標籤：其他
上一篇：obs錄屏核心流程分析