四則運算生成
項目Github地址：https://github.com/Shrouding-Potion/QuestGen
| PSP 2.1 | Personal Software Process Stages | 預(yù)估耗時(小時) | 實際耗時(小時) |
|---|---|---|---|
| Planning | 計劃 | ||
| · Estimate | · 估計這個任務(wù)需要多少時間 | 28.25 | 33.5 |
| Development | 開發(fā) | ||
| · Analysis | · 需求分析 | 1 | 1 |
| · Design Spec | · 生成設(shè)計文檔 | 1 | 0.5 |
| · Design Review | · 設(shè)計復(fù)審 | 0.25 | 0.0 |
| · Coding Standard | · 代碼規(guī)范 | 2 | 1 |
| · Design | · 具體設(shè)計 | 2 | 4 |
| · Coding | · 具體編碼 | 12 | 14 |
| · Code Review | · 代碼復(fù)審 | 3 | 3 |
| · Test | · 測試 | 5 | 6 |
| Reporting | 報告 | ||
| · Test Report | · 測試報告 | 1 | 1 |
| · Size Measurement | · 計算工作量 | 0 | 0 |
| · Postmortem & Process Improvement Plan | · 事后總結(jié)，提出過程改進計劃 | 1 | 1 |
| 合計 | 28.25 | 31.5 |
1. 任務(wù)目標
- 一階段 - 要求能生成、計算、支持真分數(shù)四則運算，同時能接受用戶輸入答案，給出總共對錯的數(shù)量。
- 二階段 - 要求能支持乘方運算并且支持
**和^兩種乘方表示方式，支持用戶通過設(shè)置來選擇。 - 三階段 - 要求將軟件實用化，做出電腦圖形界面程序、智能手機程序、網(wǎng)頁程序或者演示動畫。
2. 思路簡述
我們使用一棵二叉樹來表示一個運算表達式，如此一來，隨機的生成二叉樹就能夠生成四則運算。如下圖所示
觀察得知，一棵二叉表達式樹有以下幾個特征：
- 全樹由
算符節(jié)點和數(shù)值節(jié)點組成
- 全樹由
- 數(shù)值節(jié)點為葉子節(jié)點
- 由于四則運算為雙目運算符，算符節(jié)點都擁有左、右子樹
-
算符節(jié)點數(shù) = 數(shù)值節(jié)點數(shù) - 1
由此，我生成四則運算的思路就是，生成n個數(shù)值節(jié)點和n-1 個算符節(jié)點。
-
- 兩個列表：
filled[],unfilled[]分別保存已填充子樹的和未填充子樹的。
- 兩個列表：
- 初始時，數(shù)值節(jié)點由于不需要子樹，全放入filled中；算符節(jié)點由于需要安裝子樹，都存放在unfilled中。
- 之后，對每個unfilled列表中的元素x，從filled列表中隨機取出2個元素作為左右子樹，再將x移動到filled列表中。
- 當unfilled為空時，表達式樹構(gòu)造完成。
- 當unfilled為空時，表達式樹構(gòu)造完成。
去重
題目中有去重的要求。我們的去重方法是生成表達式樹時，將表達式的左右子樹比較大?。ū容^輸出的字串即可），若右樹大于左樹，則交換它們（僅應(yīng)用于滿足交換律的乘法、加法）。此操作自底向下遞歸進行，直至整棵樹有序。這樣，我們就可以追本溯源，將相同表達式，但異構(gòu)的樹歸為一相同的樹。
解決了異構(gòu)問題，我們就使用了Python的集合
set()操作，將樹轉(zhuǎn)為字符串存入。在產(chǎn)生新的樹時，若是集合中已存在，就意味著重復(fù)，應(yīng)當剔除。
求值
對表達式求值，同樣采用自底向下的方法 。由于任意算符節(jié)點都是對左右子樹進行運算，應(yīng)當優(yōu)先求得子樹的值。計算除法時，我們使用Python的Fraction類來實現(xiàn)。Fraction類實現(xiàn)了分數(shù)的四則運算，并含有自動約分，為我們的求值提供了極大方便
參數(shù)開關(guān)
任務(wù)要求的參數(shù)較多，我們使用getopt庫進行參數(shù)的識別
在shell中，使用main -h即可顯示幫助信息：
Usage:
-h, print this help, 顯示幫助
-n, num of expressions to generate (default: 4), 生成表達式數(shù)量
-l, num of operators in each expression (default: 4), 每個表達式的算符數(shù)
-e, enable Exponential Operator, 允許指數(shù)算符
-p, Exponential Operator print as '^' rather than '**',
指數(shù)算符輸出為 '^', 而不是'**'3
-v, verbose output, 冗長輸出 - 打印將寫入的題目和答案
-i, interactive mode, 交互模式，允許用戶輸入答案并得到正誤統(tǒng)計
我們的命令行程序支持使用-n 設(shè)定生成表達式數(shù)量，-l 設(shè)定算符數(shù)目，-e開關(guān)控制是否允許指數(shù)算符，-p設(shè)置指數(shù)算符顯示為**還是^
此外，不僅能夠輸出成文件，還可以加上-v使結(jié)果在控制臺打印
-i 交互模式是可以用戶輸入答案，程序統(tǒng)計正誤數(shù)量
GUI
圖形界面的設(shè)計，我們選用了方便快捷的PyQt5
Qt豐富的自帶控件和獨樹一幟的信號槽機制使我們方便的編寫界面邏輯
我們制作的界面如圖所示
在我們的GUI程序中，可以設(shè)置符號數(shù)、可以判斷用戶輸入對錯、擁有倒計時，倒計時結(jié)束后不會一概而論的否決用戶的作答，而是將現(xiàn)有輸入進行判斷對錯。
題目歷史可以回顧曾經(jīng)出過的題目，回顧其答案以及當時用戶是否正確作答。
3. 單元測試
我們?yōu)橹饕K的方法都進行了單元測試。我們總計設(shè)計了20個測試用例，以嘗試發(fā)掘模塊中潛在的漏洞
4. 性能分析
我們使用了cProfile對命令行程序進行了整體的性能分析
執(zhí)行使用shell命令：
python -m cProfile -s cumulative .\src\main.py -n 1000 -e -l 6 -p
這樣，我們的命令行程序會生成1000個四則運算，包含指數(shù)，算符數(shù)為6，指數(shù)符號為-^
運行時，cProfile會對我們的程序進行采樣，以分析CPU資源消耗。
從結(jié)果看出，生成算法中，耗時最長的部分是深拷貝操作（
copy.deepcopy）。該操作是去重操作的不可或缺的前置操做，其本身又是Python自帶模塊，難以進一步優(yōu)化。
5. 收獲體會
這次合作項目，我們2人分工明確，各司其職，最終圓滿的完成了任務(wù)書中的全部要求。在此我的感受頗豐，激動之心情溢于言表。我從軟件設(shè)計開始直至單測、性能分析全程參與項目，同組同學(xué)也積極完成分配到的任務(wù)，不斷地優(yōu)化他的代碼，我們一起一次又一次超出了我們一開始對項目的預(yù)期。
在項目中，我學(xué)得了分工合作的基本要領(lǐng)、實踐了課堂所學(xué)的軟件設(shè)計語言和軟件設(shè)計方法、鞏固了Python程序設(shè)計的技能。著實為我未來的職業(yè)生涯添磚加瓦，鞏固了基礎(chǔ)。
