簡單的LISP算術表達式計算器

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

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

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

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

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

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

7、chN輸出v1.pop()chi!=0?YN 結束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：計算器界面 （2）每一次輸入數(shù)據(jù)以后，都要回車再輸入ctrl+z，然后再回車，就能得到所需結果。這其中ctrl+z是結束流。首先計算6。如圖7所示。圖

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

9、對源程序作了相當大的改動，這其中包括對綴余程序的刪除，對錯誤程序的修正。另外程序參考了網上的模版，但其中不明白的地方有很多，問了很多人，也查閱了以前學過的關于棧的知識，最后也不是徹底的能弄明白。我對于我的程序不是很滿意，因為這并不是一個簡單的LISP計算器，計算器最起碼能進行四則運算，但此計算器只能完成類似題目中所給的運算。雖然程序有些欠缺的地方，但畢竟是花了十多天的時間在程序上，收獲還是很多的，算是對一學期的軟件課作了一個總結，也從搜索資料中學會了運用圖書館和網絡，總之軟件課設使我受益匪淺，對以后的工作和學習都有很大的幫助。五、程序清單#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;/使其參與運算private:int big;int

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

12、dl;cout<<" 結果：6，9，15，15，36 "<<endl;cout<<" "<<endl;cout<<" 設計者： 張強 學號：2008040201122 "<<endl;cout<<"="<<endl;cout<<" 請輸入表達式數(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<<"結果： "<<endl;cout<<v1.pop()<<endl; else if(ch