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

沈陽航空工業(yè)學(xué)院課程設(shè)計(jì)（說明書）簡單LISP算術(shù)表達(dá)式計(jì)算器班級/學(xué)號-024學(xué)生姓名田青林指導(dǎo)教師賈亮一、題目分析本題目是設(shè)計(jì)一個(gè)簡單的LISP算術(shù)表達(dá)式計(jì)算器。簡單LISP算術(shù)表達(dá)式(以下簡稱表達(dá)式)定義如下：一個(gè)0..9的整數(shù)；或者(運(yùn)算符表達(dá)式表達(dá)式)例如，6,(+45),(+(+25)8)都是表達(dá)式，其值分別為6,9和15。算術(shù)表達(dá)式不同于普通的普通的表達(dá)式，不是簡單的從左向右(或是從右向左)的計(jì)算，它包含了算術(shù)運(yùn)算符和算術(shù)量，計(jì)算的過程就是要根據(jù)算術(shù)運(yùn)算符的優(yōu)先關(guān)系將其所對應(yīng)得量的每一位進(jìn)行計(jì)算，最后得到結(jié)果。初步思想是建立一個(gè)棧列，將變量存儲進(jìn)去，通過每步中對頭兩個(gè)算術(shù)量的求和，最后將結(jié)果存儲到棧頭，輸出。運(yùn)算的要點(diǎn)如下：從左到右地掃描表達(dá)式掃描到操作數(shù)時(shí)，直接輸出。第二次掃描到'('時(shí)進(jìn)行遞歸調(diào)用，從頭進(jìn)行掃描。掃描到算術(shù)量時(shí)將其壓入棧，并與前一個(gè)壓入棧的算術(shù)量求和。最后的棧頭元素即為所求。二、設(shè)計(jì)過程(程序流程圖)根據(jù)本課設(shè)題目的要求，本設(shè)計(jì)程序依據(jù)利用棧依次從里向外計(jì)算括號內(nèi)數(shù)的思想設(shè)計(jì)成一個(gè)簡單的LISP算術(shù)表達(dá)式計(jì)算器。該程序首先建立一個(gè)棧，通過PUSH函數(shù)和POP函數(shù)的入棧，出棧功能實(shí)現(xiàn)棧中元素“先進(jìn)后出，后進(jìn)先出”的特性。然后動態(tài)建立一大小為K的整型數(shù)組，把開辟的數(shù)組指針賦給a,從而實(shí)現(xiàn)棧函數(shù)的構(gòu)造過程。然后再建立棧的對象，再建立一個(gè)字符型數(shù)組ch，然后向該數(shù)組輸入表達(dá)式，最后進(jìn)入表達(dá)式判斷階段。若LISP表達(dá)式為一操作數(shù)，則直接輸出；若該表達(dá)式為運(yùn)算符，則經(jīng)過主函數(shù)的掃描計(jì)算，最終輸出結(jié)果。2.1棧的建立這是一個(gè)子函數(shù)stack(intk=100)，首先建立一個(gè)足夠大的棧，動態(tài)定義其大小為100，然后對其置空初始化，再根據(jù)判斷其是否為空返回不同的值。其設(shè)計(jì)流程圖如圖1。

圖1：棧的建立2.2入棧這是一個(gè)子函數(shù)PUSH，首先賦給輸入值虹再判斷棧是否為非空，若為非空則將k壓入棧中；若為滿棧，則輸出錯(cuò)誤。其流程圖如圖2所示。圖2：PUSH函數(shù)2.3出棧

這是一個(gè)子函數(shù)POP,首先判斷是否非空，若是則輸出棧頭元素a[top],若不是，則返回0并參與運(yùn)算。其設(shè)計(jì)流程圖如圖3所示。圖3：POP函數(shù)2.4構(gòu)建函數(shù)首先動態(tài)開辟一個(gè)大小為K的數(shù)組，然后把開辟數(shù)組的指針賦給a,然后將K-1賦給Big,將-1賦給Top，從而實(shí)現(xiàn)函數(shù)的構(gòu)造過程，函數(shù)構(gòu)造完畢，退出此進(jìn)程，此段程序結(jié)束。其設(shè)計(jì)流程圖如圖4所示。圖4：構(gòu)建函數(shù)2.5主函數(shù)這是整個(gè)程序的核心所在。首先要建立一個(gè)棧VI，將所求表達(dá)式賦值給字符變量ch。接下來就是從頭掃描字符，這也是一個(gè)循環(huán)的過程。若ch[i]不是(’，則直接入棧，若是則跳向下下個(gè)字符，；再判斷是不是'('①，若不是，則將ch[i]入棧，跳向下一個(gè)字符；再判斷是不是'('②，若還不是則入棧。這其中①若是，②若是則都要進(jìn)行從頭掃描。接下來進(jìn)行一個(gè)總的判斷“！='('&&!=')'?”，若成立，跳向下一字符，若不成立跳過本步；接下來判斷是否為‘’，若是則把入棧的兩個(gè)元素出棧后相加再入棧，跳向下一字符。最后對此循環(huán)作一個(gè)判斷，若ch[i]是0則接著進(jìn)行循環(huán)，若不是則跳出循環(huán)輸出棧頂元素，即為所求。其設(shè)計(jì)流程如圖5所示。三、調(diào)試過程及實(shí)驗(yàn)結(jié)果3.1調(diào)試過程：本程序在調(diào)試的過程中遇到了很多問題，首先程序中有不少的綴余成分，尤其是總循環(huán)的部分本來就是一個(gè)很復(fù)雜的邏輯問題，有綴余更是會使理解難上加難，這一部分是通過一步一步調(diào)試更正的。最后得到的程序能完成題目中所給的要求。主要的主函數(shù)的修改如下圖所示。int1-H;ifCnhL-iJUK<-yM?rr.hLiJ<cout<<ch[l]<<endl:return;}/*tJhiLe(ch[i]l=QKvl.push(ch[l]->i8);i^;}whiluCtvl.uupLyt))(COUt?Vl.pup(whLL^Cchfilf-O]iifCcni-i<i-E;IlCrh[-iJ—'(■)continue;ul.pU^llCL：ll[L]-Jia)；ifcchri]-'c]cnntiintup;ul.push(ch[i;>elseif(ch[l]!-B)■)ul<pu5h(ch[l]-^8);{cnut?BB?endll;continde;}*///cnut?o1_pnp()?"1-pnp();iFCch[i]*-s)ia&ch[i]*-'(B)d;v1-push(u1.popC)i*y1-pop(n；IL—￡F[ch[i]—"(■)vldpuEh(u1Bpop());>cout?^±果；"<<pndl;cout<<v1-pop()<<endl;。叫HL.請輸入表達(dá)式數(shù)據(jù);uhile;Int1-0：whileCulifi]t=O)<<if(Eh[i]==-C>continue;3*；lFtrh[ij—'(■)continue；u1_push(ch[;ielseif(chTi]*-■)■)ul-pmti(5i]耳H);If(diri]*-')!-'(■)E；i'l(rhLiJ—-r)tU1.piJhll(u1.|iop(]*U1-|llip()];i，，；>COUW象果,"<<rnm:修改前3.2實(shí)驗(yàn)結(jié)果：修改后運(yùn)行程序之后，會看到一個(gè)如圖6所示的LISP計(jì)算器的界面，還可以看到題目要求、姓名、學(xué)號、指導(dǎo)老師等。這也是一個(gè)待輸入界面。本程序?yàn)楹唵蔚腖ISP算術(shù)表達(dá)式計(jì)算器，可以實(shí)現(xiàn)LISP加法表達(dá)式求值正確格式的測試數(shù)據(jù)：6,(+萌)，(+(+25)8),(+2(+58)),(*(*(*12)(+34))(+(+56)(+78)))結(jié)果：6,9,15,15,36設(shè)計(jì)者：張強(qiáng)學(xué)號：2008040201122=SiAiSii：=============================================圖6:計(jì)算器界面每一次輸入數(shù)據(jù)以后，都要回車再輸入ctrl+z，然后再回車，就能得到所需結(jié)果。這其中ctrl+z是結(jié)束流。首先計(jì)算6。如圖7所示。亍'C:\Users\Administrator\Desktop\V(P\Debug\l.exe"o回I本程序?yàn)楹唵蔚腖ISP算術(shù)表達(dá)式計(jì)算器，可以實(shí)現(xiàn)LISP加法表達(dá)式求值..111.■58T正確格式的測試數(shù)據(jù)：6,(*45),(+(+2S)8)(+(+〔H2)..111.■58T結(jié)果：6,9,15,15,36設(shè)計(jì)者：張強(qiáng)學(xué)號：2008040201122請輸入表達(dá)式數(shù)據(jù)：6結(jié)果：6Pressanykeytocontinue計(jì)算(+45)，如圖8所示?！?C:\Users\Administrator\De5ktop\VFP\Debug\l.exe"「本程序而簡麗I如章祿達(dá)衣開算器，可切旬LI必而注表活式求值正確格式的測試數(shù)據(jù)：6,(,4S),(+(+25)8),(+2(+58)),(+(+(+12)(+34))(+(+56)(+78)))結(jié)果：6,9,15,15,36設(shè)計(jì)者：張強(qiáng)學(xué)號：2008040201122請輸入表達(dá)式數(shù)據(jù)：<+45>箱果：pPressanykeytocontinue圖8：計(jì)算（+45）計(jì)算(+(+(+12)(+34))(+(+56)(+78))),計(jì)算過程如圖10所示。,C:\Users\Administrator\De5ktop\VlP\Debug\l.exe"本程序?yàn)楹唵蔚腖I配算術(shù)表達(dá)式計(jì)算器，可以實(shí)現(xiàn)LISP加法表達(dá)式求值正確格式的測試數(shù)據(jù)：6,(+萌)，(+(+25)8),(+2(+58)),(*(*(*12)(+34))(+(+56)(+78)))結(jié)果：6,9,15,15,36設(shè)計(jì)者：張強(qiáng)學(xué)號：2008040201122=SiAiSSi：=============================================(+<+<+12><+34>><+<+56><+78>>>結(jié)泉Pressanykeytocontinue圖10：計(jì)算(+(+(+12)(+34))(+(+56)(+78)))四、結(jié)論本程序十分簡潔，且理解上也比較容易，完成了簡單的算術(shù)表達(dá)式的計(jì)算問題，但是沒能夠?qū)崿F(xiàn)其四則運(yùn)算的問題，還有按照原思路應(yīng)該是建立兩個(gè)棧，一個(gè)存放數(shù)值，一個(gè)存放運(yùn)算符，比較運(yùn)算符的優(yōu)先級然后對其控制的值作相應(yīng)的運(yùn)算。由于本人軟件知識有限，所以得出的程序只是實(shí)現(xiàn)了片面的功能，對運(yùn)算符采取了跳過的處理方式，只對表達(dá)式中的值作和，再輸出。經(jīng)過了將近兩周的軟件課設(shè)，根據(jù)題目要求對源程序作了相當(dāng)大的改動，這其中包括對綴余程序的刪除，對錯(cuò)誤程序的修正。另外程序參考了網(wǎng)上的模版，但其中不明白的地方有很多，問了很多人，也查閱了以前學(xué)過的關(guān)于棧的知識，最后也不是徹底的能弄明白。我對于我的程序不是很滿意，因?yàn)檫@并不是一個(gè)簡單的LISP計(jì)算器，計(jì)算器最起碼能進(jìn)行四則運(yùn)算，但此計(jì)算器只能完成類似題目中所給的運(yùn)算。雖然程序有些欠缺的地方，但畢竟是花了十多天的時(shí)間在程序上，收獲還是很多的，算是對一學(xué)期的軟件課作了一個(gè)總結(jié)，也從搜索資料中學(xué)會了運(yùn)用圖書館和網(wǎng)絡(luò)，總之軟件課設(shè)使我受益匪淺，對以后的工作和學(xué)習(xí)都有很大的幫助。五、程序清單#include<iostream.h>inty=0;classstack(public:stack(intk=100){a=newint[k];big=k-1;top=-1;}boolempty(){returntop==-1;}boolfull(){returntop==big;}//入棧voidpush(intk){if(!full())a[++top]=k;else{cout<<"wrongpush"<<endl;return;}}〃出棧intpop(){if(!empty())returna[top--];elsereturn0;//使其參與運(yùn)算}private:intbig;inttop;int*a;};voidmain(){stackv1;charch[100];cout<<"本程序?yàn)楹唵蔚腖ISP算術(shù)表達(dá)式計(jì)算器，可以實(shí)現(xiàn)LISP加法表達(dá)式求值"<<endl<<endl;cout<<""<<endl;cout<<"正確格式的測試數(shù)據(jù)：6,(+45),(+(+25)8),(+2(+58)),"<<endl;cout<<"(+(+(+12)(+34))(+(+56)(+78)))"<<endl;cout<<"結(jié)果：6,9,15,15,36"<<endl;cout<<""<<endl;cout<<"設(shè)計(jì)者：張強(qiáng)學(xué)號：2008040201122"<<endl;cout<<"======================================================================"<<endl;cout<<"請輸入表達(dá)式數(shù)據(jù)："<<endl;while(cin>>ch);inti=0;while(ch[i]!=0){if(ch[i]=='('){i=i+2;if(ch[i]=='(')continue;v1.push(ch[i]-48);i++;if(ch[i]=='(')continue;v1.push(ch[i]-48);}elseif(ch[i]!=')')v1.push(ch[i]-48);if(ch[i]!=')'&&ch[i]!='('