張慧寧

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

關(guān)鍵詞：全計(jì)算過程顯示；計(jì)算器；單鏈表；算法；遞歸

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：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概述

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

2 設(shè)計(jì)思想

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

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

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

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

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

計(jì)算器的主要功能如下：

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

基本四則運(yùn)算：如+、-、*、/ 等。

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

括號運(yùn)算：（）。

3.2詞法分析設(shè)計(jì)

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

3.3語法分析設(shè)計(jì)

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

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

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

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

流程圖如圖3。

3.4運(yùn)算符優(yōu)先級判定及計(jì)算輸出設(shè)計(jì)

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

^、$為第一級運(yùn)算符；

（）、[]為二級運(yùn)算符；

*、/為三級運(yùn)算符；

+、-為四級運(yùn)算符；

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

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

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

5 結(jié)論

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

參考文獻(xiàn)：

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

[2] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)[M].2版.北京：清華大學(xué)出版社，2008.

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

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

[5] 黎遠(yuǎn)松.基于樹的遞歸算法分析技術(shù)[J]. 四川理工學(xué)院學(xué)報(bào)：自然科學(xué)版， 2012（4）.