四則運(yùn)算生成
項(xiàng)目Github地址：https://github.com/Shrouding-Potion/QuestGen
| PSP 2.1 | Personal Software Process Stages | 預(yù)估耗時(shí)(小時(shí)) | 實(shí)際耗時(shí)(小時(shí)) |
|---|---|---|---|
| Planning | 計(jì)劃 | ||
| · Estimate | · 估計(jì)這個(gè)任務(wù)需要多少時(shí)間 | 28.25 | 33.5 |
| Development | 開發(fā) | ||
| · Analysis | · 需求分析 | 1 | 1 |
| · Design Spec | · 生成設(shè)計(jì)文檔 | 1 | 0.5 |
| · Design Review | · 設(shè)計(jì)復(fù)審 | 0.25 | 0.0 |
| · Coding Standard | · 代碼規(guī)范 | 2 | 1 |
| · Design | · 具體設(shè)計(jì) | 2 | 4 |
| · Coding | · 具體編碼 | 12 | 14 |
| · Code Review | · 代碼復(fù)審 | 3 | 3 |
| · Test | · 測(cè)試 | 5 | 6 |
| Reporting | 報(bào)告 | ||
| · Test Report | · 測(cè)試報(bào)告 | 1 | 1 |
| · Size Measurement | · 計(jì)算工作量 | 0 | 0 |
| · Postmortem & Process Improvement Plan | · 事后總結(jié)芹关，提出過(guò)程改進(jìn)計(jì)劃 | 1 | 1 |
| 合計(jì) | 28.25 | 31.5 |
1. 任務(wù)目標(biāo)
- 一階段 - 要求能生成续挟、計(jì)算、支持真分?jǐn)?shù)四則運(yùn)算侥衬，同時(shí)能接受用戶輸入答案诗祸，給出總共對(duì)錯(cuò)的數(shù)量。
- 二階段 - 要求能支持乘方運(yùn)算并且支持
**和^兩種乘方表示方式轴总，支持用戶通過(guò)設(shè)置來(lái)選擇直颅。 - 三階段 - 要求將軟件實(shí)用化，做出電腦圖形界面程序怀樟、智能手機(jī)程序功偿、網(wǎng)頁(yè)程序或者演示動(dòng)畫。
2. 思路簡(jiǎn)述
我們使用一棵二叉樹來(lái)表示一個(gè)運(yùn)算表達(dá)式往堡，如此一來(lái)械荷，隨機(jī)的生成二叉樹就能夠生成四則運(yùn)算。如下圖所示
觀察得知虑灰，一棵二叉表達(dá)式樹有以下幾個(gè)特征：
- 全樹由
算符節(jié)點(diǎn)和數(shù)值節(jié)點(diǎn)組成
- 全樹由
- 數(shù)值節(jié)點(diǎn)為葉子節(jié)點(diǎn)
- 由于四則運(yùn)算為雙目運(yùn)算符吨瞎，算符節(jié)點(diǎn)都擁有左、右子樹
-
算符節(jié)點(diǎn)數(shù) = 數(shù)值節(jié)點(diǎn)數(shù) - 1
由此瘩缆，我生成四則運(yùn)算的思路就是许帐，生成n個(gè)數(shù)值節(jié)點(diǎn)和n-1 個(gè)算符節(jié)點(diǎn)薛匪。
-
- 兩個(gè)列表：
filled[],unfilled[]分別保存已填充子樹的和未填充子樹的缝裤。
- 兩個(gè)列表：
- 初始時(shí)岸夯，數(shù)值節(jié)點(diǎn)由于不需要子樹端考，全放入filled中沈撞；算符節(jié)點(diǎn)由于需要安裝子樹南用，都存放在unfilled中熙卡。
- 之后洲脂，對(duì)每個(gè)unfilled列表中的元素x斤儿，從filled列表中隨機(jī)取出2個(gè)元素作為左右子樹，再將x移動(dòng)到filled列表中恐锦。
- 當(dāng)unfilled為空時(shí)往果，表達(dá)式樹構(gòu)造完成。
- 當(dāng)unfilled為空時(shí)往果，表達(dá)式樹構(gòu)造完成。
去重
題目中有去重的要求一铅。我們的去重方法是生成表達(dá)式樹時(shí)陕贮，將表達(dá)式的左右子樹比較大小（比較輸出的字串即可）潘飘，若右樹大于左樹肮之，則交換它們（僅應(yīng)用于滿足交換律的乘法掉缺、加法）。此操作自底向下遞歸進(jìn)行戈擒，直至整棵樹有序眶明。這樣，我們就可以追本溯源筐高，將相同表達(dá)式搜囱，但異構(gòu)的樹歸為一相同的樹。
解決了異構(gòu)問(wèn)題柑土，我們就使用了Python的集合
set()操作犬辰，將樹轉(zhuǎn)為字符串存入。在產(chǎn)生新的樹時(shí)冰单，若是集合中已存在幌缝，就意味著重復(fù)，應(yīng)當(dāng)剔除诫欠。
求值
對(duì)表達(dá)式求值涵卵，同樣采用自底向下的方法 。由于任意算符節(jié)點(diǎn)都是對(duì)左右子樹進(jìn)行運(yùn)算荒叼，應(yīng)當(dāng)優(yōu)先求得子樹的值轿偎。計(jì)算除法時(shí)，我們使用Python的Fraction類來(lái)實(shí)現(xiàn)被廓。Fraction類實(shí)現(xiàn)了分?jǐn)?shù)的四則運(yùn)算坏晦，并含有自動(dòng)約分，為我們的求值提供了極大方便
參數(shù)開關(guān)
任務(wù)要求的參數(shù)較多嫁乘，我們使用getopt庫(kù)進(jìn)行參數(shù)的識(shí)別
在shell中昆婿，使用main -h即可顯示幫助信息：
Usage:
-h, print this help, 顯示幫助
-n, num of expressions to generate (default: 4), 生成表達(dá)式數(shù)量
-l, num of operators in each expression (default: 4), 每個(gè)表達(dá)式的算符數(shù)
-e, enable Exponential Operator, 允許指數(shù)算符
-p, Exponential Operator print as '^' rather than '**',
指數(shù)算符輸出為 '^', 而不是'**'3
-v, verbose output, 冗長(zhǎng)輸出 - 打印將寫入的題目和答案
-i, interactive mode, 交互模式，允許用戶輸入答案并得到正誤統(tǒng)計(jì)
我們的命令行程序支持使用-n 設(shè)定生成表達(dá)式數(shù)量蜓斧，-l 設(shè)定算符數(shù)目仓蛆，-e開關(guān)控制是否允許指數(shù)算符，-p設(shè)置指數(shù)算符顯示為**還是^
此外挎春，不僅能夠輸出成文件看疙，還可以加上-v使結(jié)果在控制臺(tái)打印
-i 交互模式是可以用戶輸入答案，程序統(tǒng)計(jì)正誤數(shù)量
GUI
圖形界面的設(shè)計(jì)直奋，我們選用了方便快捷的PyQt5
Qt豐富的自帶控件和獨(dú)樹一幟的信號(hào)槽機(jī)制使我們方便的編寫界面邏輯
我們制作的界面如圖所示
在我們的GUI程序中能庆，可以設(shè)置符號(hào)數(shù)、可以判斷用戶輸入對(duì)錯(cuò)脚线、擁有倒計(jì)時(shí)搁胆，倒計(jì)時(shí)結(jié)束后不會(huì)一概而論的否決用戶的作答，而是將現(xiàn)有輸入進(jìn)行判斷對(duì)錯(cuò)。
題目歷史可以回顧曾經(jīng)出過(guò)的題目丰涉，回顧其答案以及當(dāng)時(shí)用戶是否正確作答拓巧。
3. 單元測(cè)試
我們?yōu)橹饕K的方法都進(jìn)行了單元測(cè)試。我們總計(jì)設(shè)計(jì)了20個(gè)測(cè)試用例一死，以嘗試發(fā)掘模塊中潛在的漏洞
4. 性能分析
我們使用了cProfile對(duì)命令行程序進(jìn)行了整體的性能分析
執(zhí)行使用shell命令：
python -m cProfile -s cumulative .\src\main.py -n 1000 -e -l 6 -p
這樣肛度，我們的命令行程序會(huì)生成1000個(gè)四則運(yùn)算，包含指數(shù)投慈，算符數(shù)為6承耿，指數(shù)符號(hào)為-^
運(yùn)行時(shí)，cProfile會(huì)對(duì)我們的程序進(jìn)行采樣伪煤，以分析CPU資源消耗加袋。
從結(jié)果看出，生成算法中抱既，耗時(shí)最長(zhǎng)的部分是深拷貝操作（
copy.deepcopy）职烧。該操作是去重操作的不可或缺的前置操做，其本身又是Python自帶模塊防泵，難以進(jìn)一步優(yōu)化蚀之。
5. 收獲體會(huì)
這次合作項(xiàng)目，我們2人分工明確捷泞，各司其職足删，最終圓滿的完成了任務(wù)書中的全部要求。在此我的感受頗豐锁右，激動(dòng)之心情溢于言表失受。我從軟件設(shè)計(jì)開始直至單測(cè)、性能分析全程參與項(xiàng)目咏瑟，同組同學(xué)也積極完成分配到的任務(wù)拂到，不斷地優(yōu)化他的代碼，我們一起一次又一次超出了我們一開始對(duì)項(xiàng)目的預(yù)期响蕴。
在項(xiàng)目中谆焊，我學(xué)得了分工合作的基本要領(lǐng)、實(shí)踐了課堂所學(xué)的軟件設(shè)計(jì)語(yǔ)言和軟件設(shè)計(jì)方法浦夷、鞏固了Python程序設(shè)計(jì)的技能。著實(shí)為我未來(lái)的職業(yè)生涯添磚加瓦辜王，鞏固了基礎(chǔ)劈狐。
