簡(jiǎn)單的LISP算術(shù)表達(dá)式計(jì)算器

1、沈陽(yáng)航空工業(yè)學(xué)院課 程 設(shè) 計(jì)（說(shuō)明書）簡(jiǎn)單LISP 算術(shù)表達(dá)式計(jì)算器 班級(jí) / 學(xué)號(hào) 7402101-024 學(xué) 生 姓 名 田青林 指 導(dǎo) 教 師 賈亮 一、 題目分析 本題目是設(shè)計(jì)一個(gè)簡(jiǎn)單的LISP算術(shù)表達(dá)式計(jì)算器。 簡(jiǎn)單LISP算術(shù)表達(dá)式（以下簡(jiǎn)稱表達(dá)式）定義如下: (1) 一個(gè)0.9的整數(shù)；或者 (2) （運(yùn)算符 表達(dá)式 表達(dá)式） 例如，6，（+45），（+（+25）8）都是表達(dá)式，其值分別為6，9和15。算術(shù)表達(dá)式不同于普通的普通的表達(dá)式，不是簡(jiǎn)單的從左向右（或是從右向左）的計(jì)算， 它包含了算術(shù)運(yùn)算符和算術(shù)量，計(jì)算的過(guò)程就是要根據(jù)算術(shù)運(yùn)算符的優(yōu)先關(guān)系將其所對(duì)應(yīng)得量的每一位

2、進(jìn)行計(jì)算，最后得到結(jié)果。初步思想是建立一個(gè)棧列，將變量存儲(chǔ)進(jìn)去，通過(guò)每步中對(duì)頭兩個(gè)算術(shù)量的求和，最后將結(jié)果存儲(chǔ)到棧頭，輸出。運(yùn)算的要點(diǎn)如下：從左到右地掃描表達(dá)式（1） 掃描到操作數(shù)時(shí),直接輸出。（2） 第二次掃描到（時(shí)進(jìn)行遞歸調(diào)用，從頭進(jìn)行掃描。（3） 掃描到算術(shù)量時(shí)將其壓入棧，并與前一個(gè)壓入棧的算術(shù)量求和。（4） 最后的棧頭元素即為所求。二、 設(shè)計(jì)過(guò)程（程序流程圖） 根據(jù)本課設(shè)題目的要求，本設(shè)計(jì)程序依據(jù)利用棧依次從里向外計(jì)算括號(hào)內(nèi)數(shù)的思想設(shè)計(jì)成一個(gè)簡(jiǎn)單的LISP算術(shù)表達(dá)式計(jì)算器。該程序首先建立一個(gè)棧，通過(guò)PUSH函數(shù)和POP函數(shù)的入棧，出棧功能實(shí)現(xiàn)棧中元素“先進(jìn)后出，后進(jìn)先出”的特性。然后動(dòng)

3、態(tài)建立一大小為K的整型數(shù)組，把開辟的數(shù)組指針賦給a,從而實(shí)現(xiàn)棧函數(shù)的構(gòu)造過(guò)程。然后再建立棧的對(duì)象，再建立一個(gè)字符型數(shù)組ch，然后向該數(shù)組輸入表達(dá)式，最后進(jìn)入表達(dá)式判斷階段。若LISP表達(dá)式為一操作數(shù)，則直接輸出；若該表達(dá)式為運(yùn)算符，則經(jīng)過(guò)主函數(shù)的掃描計(jì)算，最終輸出結(jié)果。2.1棧的建立這是一個(gè)子函數(shù)stack(int k=100)，首先建立一個(gè)足夠大的棧，動(dòng)態(tài)定義其大小為100，然后對(duì)其置空初始化，再根據(jù)判斷其是否為空返回不同的值。其設(shè)計(jì)流程圖如圖1。 開始 定義棧a 初始化棧a N是否為空？Y Top=big Top=-1返回top 圖1：棧的建立 2.2入棧這是一個(gè)子函數(shù)PUSH，首先賦給輸

4、入值k，再判斷棧是否為非空，若為非空則將k壓入棧中；若為滿棧，則輸出錯(cuò)誤。其流程圖如圖2所示。 開始 輸入k值 N !full( )？Ywrong pushatop=k top+ 返回 圖2：PUSH函數(shù)2.3出棧這是一個(gè)子函數(shù)POP，首先判斷是否非空，若是則輸出棧頭元素atop，若不是，則返回0并參與運(yùn)算。其設(shè)計(jì)流程圖如圖3所示。 開始!empty( )？返回0 返回atop top- 結(jié)束圖3：POP函數(shù)2.4構(gòu)建函數(shù)首先動(dòng)態(tài)開辟一個(gè)大小為K的數(shù)組，然后把開辟數(shù)組的指針賦給a,然后將K-1賦給Big,將-1賦給Top，從而實(shí)現(xiàn)函數(shù)的構(gòu)造過(guò)程，函數(shù)構(gòu)造完畢，退出此進(jìn)程，此段程序結(jié)束。其設(shè)計(jì)流

5、程圖如圖4所示。 開始動(dòng)態(tài)開辟一個(gè)大小為k的數(shù)組把開辟數(shù)組的指針賦給a big=k-1 top=-1 結(jié)束 圖4：構(gòu)建函數(shù)2.5主函數(shù)這是整個(gè)程序的核心所在。首先要建立一個(gè)棧V1，將所求表達(dá)式賦值給字符變量ch。接下來(lái)就是從頭掃描字符，這也是一個(gè)循環(huán)的過(guò)程。若chi不是（，則直接入棧，若是則跳向下下個(gè)字符，；再判斷是不是（，若不是，則將chi入棧，跳向下一個(gè)字符；再判斷是不是（，若還不是則入棧。這其中若是，若是則都要進(jìn)行從頭掃描。接下來(lái)進(jìn)行一個(gè)總的判斷“！=（&&！=)?”, 若成立，跳向下一字符，若不成立跳過(guò)本步；接下來(lái)判斷是否為），若是則把入棧的兩個(gè)元素出棧后相加再入棧，跳

6、向下一字符。最后對(duì)此循環(huán)作一個(gè)判斷，若chi是0則接著進(jìn)行循環(huán)，若不是則跳出循環(huán)輸出棧頂元素，即為所求。其設(shè)計(jì)流程如圖5所示。三、調(diào)試過(guò)程及實(shí)驗(yàn)結(jié)果 3.1調(diào)試過(guò)程：本程序在調(diào)試的過(guò)程中遇到了很多問(wèn)題，首先程序中有不少的綴余成分，尤其是總循環(huán)的部分本來(lái)就是一個(gè)很復(fù)雜的邏輯問(wèn)題，有綴余更是會(huì)使理解難上加難，這一部分是通過(guò)一步一步調(diào)試更正的。最后得到的程序能完成題目中所給的要求。主要的主函數(shù)的修改如下圖所示。 修改前 修改后3.2實(shí)驗(yàn)結(jié)果：（1）運(yùn)行程序之后，會(huì)看到一個(gè)如 圖6所示的LISP計(jì)算器的界面，還可以看到題目要求、姓名、學(xué)號(hào)、指導(dǎo)老師等。這也是一個(gè)待輸入界面。 開始建立棧V1 i=0輸入

7、chN輸出v1.pop()chi!=0?YN 結(jié)束chi='('?Ychi!=')'？ i=i+2chi='c'?YN將chi入棧i=i+1Nchi='c'?Y將chi入棧Nchi!=')'&&chi!='('？Y i=i+1chi=')'?YNv1.push(v1.pop()+v1.pop();i+ 圖5:主函數(shù)圖6：計(jì)算器界面 （2）每一次輸入數(shù)據(jù)以后，都要回車再輸入ctrl+z，然后再回車，就能得到所需結(jié)果。這其中ctrl+z是結(jié)束流。首先計(jì)算6。如圖7所示。圖

8、7：計(jì)算“6” （3）計(jì)算（+45），如圖8所示。圖8：計(jì)算（+45） （4）計(jì)算（+（+（+12）（+34）（+（+56）（+78），計(jì)算過(guò)程如圖10所示。圖10：計(jì)算（+（+（+12）（+34）（+（+56）（+78）四、結(jié)論 本程序十分簡(jiǎn)潔，且理解上也比較容易，完成了簡(jiǎn)單的算術(shù)表達(dá)式的計(jì)算問(wèn)題，但是沒能夠?qū)崿F(xiàn)其四則運(yùn)算的問(wèn)題，還有按照原思路應(yīng)該是建立兩個(gè)棧，一個(gè)存放數(shù)值，一個(gè)存放運(yùn)算符，比較運(yùn)算符的優(yōu)先級(jí)然后對(duì)其控制的值作相應(yīng)的運(yùn)算。由于本人軟件知識(shí)有限，所以得出的程序只是實(shí)現(xiàn)了片面的功能，對(duì)運(yùn)算符采取了跳過(guò)的處理方式，只對(duì)表達(dá)式中的值作和，再輸出。經(jīng)過(guò)了將近兩周的軟件課設(shè)，根據(jù)題目要求

9、對(duì)源程序作了相當(dāng)大的改動(dòng)，這其中包括對(duì)綴余程序的刪除，對(duì)錯(cuò)誤程序的修正。另外程序參考了網(wǎng)上的模版，但其中不明白的地方有很多，問(wèn)了很多人，也查閱了以前學(xué)過(guò)的關(guān)于棧的知識(shí)，最后也不是徹底的能弄明白。我對(duì)于我的程序不是很滿意，因?yàn)檫@并不是一個(gè)簡(jiǎn)單的LISP計(jì)算器，計(jì)算器最起碼能進(jìn)行四則運(yùn)算，但此計(jì)算器只能完成類似題目中所給的運(yùn)算。雖然程序有些欠缺的地方，但畢竟是花了十多天的時(shí)間在程序上，收獲還是很多的，算是對(duì)一學(xué)期的軟件課作了一個(gè)總結(jié)，也從搜索資料中學(xué)會(huì)了運(yùn)用圖書館和網(wǎng)絡(luò)，總之軟件課設(shè)使我受益匪淺，對(duì)以后的工作和學(xué)習(xí)都有很大的幫助。五、程序清單#include<iostream.h>in

10、t y=0;class stackpublic:stack(int k=100)a=new intk; big=k-1; top=-1;bool empty()return top=-1;bool full()return top=big; /入棧void push(int k) if(!full() a+top=k; else cout<<"wrong push"<<endl; return;/出棧int pop()if(!empty() return atop-; else return 0;/使其參與運(yùn)算private:int big;int

11、top;int*a;void main()stack v1;char ch100;cout<<"本程序?yàn)楹?jiǎn)單的LISP算術(shù)表達(dá)式計(jì)算器，可以實(shí)現(xiàn)LISP加法表達(dá)式求值"<<endl<<endl;cout<<" "<<endl;cout<<" 正確格式的測(cè)試數(shù)據(jù)：6，（+45），（+（+25）8），（+2（+58）， "<<endl;cout<<" （+（+（+12）（+34）（+（+56）（+78）"<<en

12、dl;cout<<" 結(jié)果：6，9，15，15，36 "<<endl;cout<<" "<<endl;cout<<" 設(shè)計(jì)者： 張強(qiáng) 學(xué)號(hào)：2008040201122 "<<endl;cout<<"="<<endl;cout<<" 請(qǐng)輸入表達(dá)式數(shù)據(jù)： "<<endl;while(cin>>ch);int i=0;while(chi!=0) if(chi='(

13、') i=i+2; if(chi='(') continue; v1.push(chi-48); i+; if(chi='(') continue; v1.push(chi-48); else if(chi!=')')v1.push(chi-48); if(chi!=')'&&chi!='(') i+; if(chi=')')v1.push(v1.pop()+v1.pop(); i+; cout<<"結(jié)果： "<<endl;cout<<v1.pop()<<endl; else if(ch