基于單鏈表的顯示全計算過程計算器的設計

張慧寧

摘要：該文對過程全顯示計算器的算法進行分析和探討，采用單鏈表實現(xiàn)顯示計算全過程的計算器。該計算器通過詞法和語法分析，對數(shù)據(jù)和運算符分別進行拆分并存儲于單鏈表中，采用遞歸運算，得到計算過程，運算后遍歷輸出，直至得到最終結果。支持的運算功能有：四則運算、括號運算、冪運算等。過程全顯示計算器解決了常見計算器只能顯示計算結果的問題。

關鍵詞：全計算過程顯示；計算器；單鏈表；算法；遞歸

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2015）34-0097-02

Abstract： In this paper ，we analyzed and discussed the calculators algorithm， using single table show the whole process of calculator to calculate. The calculator， the data and operator split respectively and stored in a single table by lexical and syntax analysis， using recursive algorithm， get the calculation process， then operation after traversal output， until get the final result. Support operation function are： arithmetic， bracket operation， power operation， etc. Process all the calculator have solved the problem of common calculator can only display results.

Key words： show the whole calculate process； calculator； single table； algorithm； recursive

1概述

計算器是生活和辦公中最常用的工具之一，有著強大的計算功能以及便攜等特性，使用場所非常廣泛。目前市面上流通的計算器絕大部分都只能顯示計算結果，對于計算過程的描述不做顯示，對使用造成很多不便。為此，本文基于單鏈表對現(xiàn)有計算器進行改進，使其能顯示每一步的計算過程，解決了計算器只能顯示計算結果問題。

2 設計思想

系統(tǒng)首先對輸入的計算過程進行詞法分析，其任務是從左到右逐步掃描計算過程，并將其獨立拆分為一個個具有完整意義的數(shù)據(jù)（1、2、3……等）、運算符（+、-、*、/、（）、[]等）。

其次，系統(tǒng)對拆分出來的數(shù)據(jù)進行語法分析。在這一步，系統(tǒng)在詞法分析的基礎上，對拆分出來的數(shù)據(jù)和運算符進行語法分析，主要功能是，判斷輸入數(shù)據(jù)是否合法（是否包含字母、中文等非法數(shù)據(jù)），判斷運算符運用是否合理，是否有出現(xiàn)類似++、--、[+]等錯誤使用運算符情況，如無誤，將數(shù)據(jù)和運算符依次存出單鏈表中。

最后，在保證語法無誤后，遍歷鏈表，判斷運算符優(yōu)先級，根據(jù)運算符優(yōu)先級進行計算，并將結果存放回鏈表，單步遍歷運算后得到的鏈表并輸出單步計算結果，顯示單步計算后的表達式信息，通過遞歸這一操作，直至運算符數(shù)目為0，則此步驟為最終結果，同時得到所有運算過程。

3 系統(tǒng)具體實現(xiàn)

3.1系統(tǒng)主要功能

計算器的主要功能如下：

運算表達式語法錯誤與否判斷：如1+1、3*8、（20+10）^2等為正確表達式，可正常往下運行；而對于（*1）、^2+3、1+++5等則為錯誤表達式，計算器會提示用戶輸入運算表達式錯誤，要求用戶重新輸入。

基本四則運算：如+、-、*、/ 等。

指數(shù)冪運算等：主要是次方（^）、二次方根（$）等。

括號運算：（）。

3.2詞法分析設計

詞法分析從左到右依次掃描運算表達式，將表達式切割為數(shù)據(jù)和運算符，主要步驟如下：讀取第一位字符，判斷數(shù)據(jù)還是表達式；接著讀取第二位，判斷數(shù)據(jù)還是表達式，如果跟前一位類型相同，則繼續(xù)讀取下一位字符，直至后一位同前一位不同為數(shù)據(jù)或表達式，切割，存入單鏈表，然后繼續(xù)從下一位字符開始進行遞歸操作，直至結束。流程圖如下：

3.3語法分析設計

語法分析遍歷單鏈表，依次判斷表達式是否符合語法，若不符合，反饋錯誤信息。具體步驟如下：

1）判斷第一位是否為符號，若是，則錯誤，反饋錯誤信息，否則，繼續(xù)；

2）判斷是否出現(xiàn)雙符號或者多符號，若出現(xiàn)，則錯誤，返回錯誤信息，否則，繼續(xù)；

3）判斷最后一位是否為符號位，所是，則錯誤，反饋錯誤信息，否則，結束。

流程圖如圖3。

3.4運算符優(yōu)先級判定及計算輸出設計

運算符優(yōu)先級判定主要是根據(jù)數(shù)學運算規(guī)則對運算符優(yōu)先級進行判定，并根據(jù)高優(yōu)先級先運算原則進行運算。運算符優(yōu)先級定義如下：

^、$為第一級運算符；

（）、[]為二級運算符；

*、/為三級運算符；

+、-為四級運算符；

運算時，先判定是否有上一級運算符，如有，則先計算上一級運算符，并將上一級運算符計算所得結果存回單鏈表中，然后遍歷輸出，遞歸執(zhí)行，直至運算符數(shù)目為0，所得結果即為最終結果。具體如下：

遍歷整個單鏈表，判斷是否有第一級運算符，如有，則進行第一級運算符運算，得到運算結果，假設運算符所在位置為N，則將結果保存到N-1節(jié)點中，接著刪除N、N+1節(jié)點，遍歷鏈表并輸出，得到一級運算符計算過程。

重復步驟，依次判斷是否有第二級運算符，第三級運算符，第四級運算符直至運算符數(shù)目為空，所得結果即為最終結果，運算結束。具體流程圖如下：

5 結論

本文基于常用的數(shù)據(jù)結構單鏈表，拓展生活中最常用的計算器的功能，使其能顯示計算過程，雖然其目前功能較為簡單，但由于其基于詞法分析，較容易拓展。由于使用單鏈表結構，沒有運算字符上限，較為實用。

參考文獻：

[1] Cormen T H，Leiserson C E，Rivest R L，ed al.算法導論[M].3版.北京：機械工業(yè)出版社，2012.

[2] 嚴蔚敏.數(shù)據(jù)結構[M].2版.北京：清華大學出版社，2008.

[3] 戴建國.遞歸算法應用分析[J].軟件設計開發(fā)，2008（28）.

[4] 張耀民.遞歸法在程序設計中的應用與分析[J].設計研發(fā)，2013（13）.

[5] 黎遠松.基于樹的遞歸算法分析技術[J]. 四川理工學院學報：自然科學版， 2012（4）.