算法表達式語法檢查

1、中南民族大學 計算機科學學院課程設計報告課程數(shù)據(jù)結構題目算法表達式語法檢查年級2014專業(yè)軟件工程學生柳真學號2073指導教師劉賽2015年12月20 日中南民族大學計算機科學學院本科課程設計任務書設計名稱：算術表達式語法檢查指導教師：/下達時間：2015-11-30學生姓名：學號:：年級專業(yè)：2014級軟件工程一、課程設計的基本要求利用數(shù)據(jù)結構課程的相關知識完成一個具有一定難度的綜合設計題目， 利用C/C+語言進行程序設計，并規(guī)范地完成課程設計報告。通過課程設計，鞏 固和加深對線性表、棧、隊列、字符串、樹、圖、查找、排序等理論知識的理 解；掌握現(xiàn)實復雜問題的分析建模和解決方法（包括問題描述、

2、系統(tǒng)分析、設計 建模、代碼實現(xiàn)、結果分析等）；提高利用計算機分析解決綜合性實際問題的基 本能力。具體要求如下：1、對現(xiàn)實復雜問題中的數(shù)據(jù)對象特性及組織方法進行分析和研究，設計 適當?shù)臄?shù)據(jù)邏輯結構、存貯結構以及相應運算操作，把現(xiàn)實世界問題建模轉化為 計算機內部表示并進行處理。2、采取模塊化方式進行程序設計，要求程序的功能設計、數(shù)據(jù)結構設計 及整體結構設計合理。學生也可根據(jù)自己對題目的理解增加新的功能模塊（視情 況可另外加分）。3、系統(tǒng)以菜單界面方式（至少采用文本菜單界面，如能采用圖形菜單界 面更好）工作，運行界面友好，演示程序以用戶和計算機的對話方式進行，利用 文件進行數(shù)據(jù)的提取與存儲。4、程序

3、算法說明清晰，理論分析與計算正確，運行情況良好，實驗測試 數(shù)據(jù)無誤，容錯性強（能對錯誤輸入進行判斷控制）。5、編程風格良好（包括縮進、空行、適當注釋、變量名和函數(shù)名見名知 意，程序容易閱讀等）；6 寫出規(guī)范的課程設計報告，具體要求見相關說明文檔。二、課程設計的主要內容題目描述：算術表達式語法檢查。功能要求及說明：（1）鍵盤讀入一個四則運算算術表達式，對其進行語法檢查；（2）算術表達式允許嵌套，如果出錯，指出出錯位置；（3）不需要計算結果；（4）盡量不使用棧。三、課程設計的進程安排1. 2015年11月30日：布置并下達課程設計題目。2. 2015年12月7日之前：聯(lián)系指導教師，理解課程設計題目

4、及相關要 求，查閱相關資料，進行課程設計 （地點：9-204，9-206）。3. 2015年12月7日至12月31日（第15周-第 18周）：課程設計源程序的調試、修改與檢查，書寫課程設計報告（地點：計算機科學學院實驗機房）。4. 2016年12月31日之前：上交、檢查設計報告 （地點：計算機科學學院 實驗機房）。'指導教師：2015 年 11 月 20日算術表達式語法檢查一 目的根據(jù)課題要求，完成算法表達式語法檢查。具體完成以下四點要求：（1）鍵盤讀入一個四則運算算術表達式，對其進行語法檢查；（2）算術表達式允許嵌套，如果出錯，指出出錯位置；（3）不需要計算結果；（4 ）盡量不使用棧

5、。二需求分析1、選擇存放算術表達式的數(shù)據(jù)結構本次課設，我選擇了本學期數(shù)據(jù)結構中所學的棧來實現(xiàn)算術表達式中的字符存放。2、運算符優(yōu)先級劃分一個完整的算術表達式中包含 +、-、*、/、（、）六種運算符，當遇到這些字符時要確 定其優(yōu)先級的高低，并依次存放進?；蛘叱鰲?。并且還可以進行發(fā)現(xiàn)輸入錯誤提示判斷， 達到課題中相關要求。三概要設計1、運算符優(yōu)先級等級劃分表+-*/()#+11-1-1-111-11-1-1-111*1111-111/1111-111(-1-1-1-1-10-3)1111-111 /#-1 -1-1-1-1-20 /上表中1代表棧中運算符出棧，進行運算； 0代表棧中運算符（或#&#

6、39;）出 棧；-1代表當前運算符進棧；-2代表當前輸入）錯誤；-3代表算術表達式末尾少輸 入）。2、程序流程圖定義一個棧A，用來存放數(shù)字；定義一個棧 B用來存放運算符定義一個字符變量c, 一個字符數(shù)組d100從表達式首字符開始，獲取一個字符存放 到c中，開始依次檢查檢查下一個字符1 Tb = 0B中運算符出棧ir進行下一個字符檢查1F跳出本次循環(huán)，進 行下一次循環(huán)否b = -2否b = -3丄進行下一個字符檢查1r跳出本次循環(huán)，進 行下一次循環(huán)是報錯，輸入''錯誤報錯，輸入非法字符B中運算符出棧，并報 錯。第i位少輸入'檢查下一個字符跳出本次循環(huán)，進行下 一次循環(huán)結束

7、跳出本次循環(huán)，進 行下一次循環(huán)四詳細設計1、棧的結構及相關功能函數(shù)構造偽代碼typedef int SEIemType;con st int STACK_INIT_SIZE = 100; / 存儲空間初始分配量 con st int STACKINCREMENT = 10;/ 存儲空間分配增量typedef struct/ '.SElemType *base; /棧底指針，在棧構造前和銷毀后，其值均為空SElemType *top; / 棧頂指針/ int stacksize; /當前已分配的存儲空間SqStack;/構造一個空棧void InitStack(SqStack &

8、S);若棧不為空，返回棧頂元素值SElemType GetTop(SqStack & S);插入元素e為棧的新棧頂元素void push(SqStack & S,SElemType e);/用e返回棧頂元素，并刪除棧頂元素void Pop(SqStack & S,SElemType & e);2、實現(xiàn)表達式語法檢查功能函數(shù)構造偽代碼/判定輸入的運算符，并分類標記int judgePrecede nce(char a)int i = 7;switch(a)case '+': i =0; break;case '-': i =1; b

9、reak;case '*': i =:2; break;case '/': i =3; break;case '(': i =4; break;case ')': i =5; break;case '#': i =6; break;return i;/比較運算符的優(yōu)先級，并標記分類int Precede nce(char a,char b)根據(jù)judgePrecedenee ()函數(shù)確定 a、b的運算符種類，然后構建一個7*7的二維數(shù)組表，依次填入優(yōu)先級，并返回相應優(yōu)先等級。具體表格信息見概要設計中 /運算符優(yōu)先等

10、級劃分表。'/執(zhí)行運算int Operate(i nt a,char b,i nt c)其中a、c是數(shù)字，b是運算符(+、-、*、/)，實現(xiàn)具體運算操作，并返回 運算結果值。/判斷c是否是運算符int pan dua n( char c)根據(jù)judgePrecedenee ()函數(shù)，判斷 c是否是運算符，如果是怎返回1否 則返回0。/具體應用操作void Yun sua n()SqStack A,B;/ 創(chuàng)建棧 A、Bpush(B,#);/棧B中棧底存入#c = getchar();/獲取算術表達式中字符int i = 1;while(c !='#' | GetTop(

11、B)!='#')if(i = 1 && judgePrecede nce(c) != 7)首字符是運算符，報錯；if(c >= 'O' && c <= 9)/字符是數(shù)字，存放在數(shù)組 d1OO中，后轉化為數(shù)字存入/ 棧A中；else if(judgePrecede nce(c) != 7)/字符是運算符，進行判斷，有錯則報錯，沒有則進棧B；else報錯，輸入非法字符。五調試分析1、算法邏輯問題及輸出錯誤檢查一個算術表達式錯誤時，要具體要第幾位以及是哪些錯誤，在剛開始的檢查功能 檢查設計的時候，我的代碼只能檢查到+、-、*

12、、/相關輸入錯誤，對于(、)運算符不能完全檢查出輸入錯誤，其中有關除數(shù)為 0的輸入錯誤時，程序不能檢查除數(shù)0后面表達式中的錯誤，直接程序終止。后來，我在程序加了一個條件關于除數(shù)為0的運算限定，成功解決了除數(shù)為0后面表達式的語法無法檢查的問題。其中，最為重要的是，通過設計不同類型的算術表達式進行 語法檢查，不斷地發(fā)現(xiàn)程序設計過程中的邏輯錯誤，并不斷修改，最后成功解決了本次課 設中難點。六測試結果1、設計輸入的算術表達式(1) +-*/1+2/(4-4*2/4)(2) (3a+2b)*4-8/2(3) a!c1+2a*(3-4/2)(4) 1+2 3*(4/5)(5) 1+2*(2*4/0-3)(

13、6) 1+2*(3-4/2(7) 1-2/(3-4*2)(8) 2*3+)(3/3-4)(9) 2+4-5*(3+2+(2*1)(10) (2+4)-5/0*(3+2*(2+1)2、具體運算檢查分析結果截圖圖一：(按璋勢束)：alcl+2a*<3-4/2>lt 盤完畢，己退出！己退算術表達式(按束)：*2Z<4-4w2Z4>«Ji ' t：OOOV< 韜苗生勺 MyProje-ctsFttDe bugi, 1-exe*!.！ BAbbL鮒 I- 2”！- -ra峯盍 一_一一一 一一一p mt-111TJ4IX 位fe-g-恆冷 12 3( 式克

14、 結退 Bi畢完查檢 込誤2喀咲誤法匕 己主卜鬼謐mzzt;算術表*式語法臉查完畢：已退岀| ! !算術表幺式語漣戍直完畢：已退岀| ! ! EOOOVCWMy Pgjea 沁干眇氐 bugl 日 hkLlbTj上圖一是設計輸入的算術表達式(1) (4)運行結果截圖;圖二：退 已算少達 As 輸11木 惰第算吃| r曲 H!退 ryKOJ + 口肯r M，檢 達入注 表Alt衰 輸1U木 請弟R己退出上圖二是設計輸入的算術表達式(5) (8)運行結果截圖;圖三：2達矗法 衷蹩人語 徇3Q1419木 請式S 退 已達展人飭 4<7'丄 2 / 請fssskb上圖三是輸入設計的算術表

15、達式（9） （10）運行結果截圖。七用戶使用說明1、輸入規(guī)則輸入一個算術表達式，其中對應的運算符是+、-、*、/、（、）表達的意思是加、減、乘、除、順括號、反括號。要求輸入一個算術表達式完畢后，在輸入一個#'結束輸入，最后按enter鍵即可得到算術表達式語法檢查結果。八課程設計總結在本次課程設計實施的過程中，遇到了很多問題，當然收獲也很多。起初，讓我感覺很難的地方在于如何確定算術表達式錯誤的位置以及有哪些錯誤要確定。在此過程中，我用了一個整形變量來計算依次檢查的字符數(shù)，來確定錯誤的具體位置。其中錯誤的類型要分類進行查找，在算法實施之前我把錯誤類型進行分類，并初步畫 出算法的程序流程圖，

16、不斷反復推敲和檢查，從中也發(fā)現(xiàn)了我很多邏輯上的錯誤。通過不斷修改和測試，也讓我設計的核心功能函數(shù)不斷完善，最終達到課題的要求。附具體源碼：#in clude<iostream>#in clude<cstdio>#in clude<cstdlib>using n amespace std;typedef int SEIemType;const int STACK_INIT_SIZE = 100; / 存儲空間初始分配量const int STACKINCREMENT = 10;/ 存儲空間分配增量typedef structSElemType *base; /

17、棧底指針，在棧構造前和銷毀后，其值均為空SElemType *top; / 棧頂指針int stacksize; /當前已分配的存儲空間SqStack;/構造一個空棧void InitStack(SqStack &S);/若棧不為空，返回棧頂元素值SElemType GetTop(SqStack & S);/插入元素e為棧的新棧頂元素void push(SqStack & S,SElemType e);/用e返回棧頂元素，并刪除棧頂元素void Pop(SqStack & S,SElemType &e);/判定輸入的運算符，并分類標記int judgeP

18、recede nce(char a);/比較運算符的優(yōu)先級，并標記分類int Precede nce(char a,char b);/執(zhí)行運算int Operate(i nt a,char b,i nt c);/判斷c是否是運算符int pan dua n( char c);/具體應用操作void Yun sua n();int mai n()while(1)cout<<"請輸入算術表達式(按#結束)："Yun sua n();/* cout<<"繼續(xù)輸入算術表達式請輸入$，退出請輸入#： "<<endl;char i

19、;cin> >i;if(i = # )break;*/return 0;void InitStack(SqStack &S)=(SEIemType *)malloc(STACK_INIT_SIZE*sizeof(SEIemType);一,=STACK_INIT_SIZE;return ;SElemType GetTop(SqStack & S)if = retur n 0;return *;void push(SqStack & S,SElemType e) if - >=(SElemType * )realloc,+ STACKINCREMENT)

20、* sizeof(SElemType);if(! exit(0);=+ ;+= STACKINCREMENT;*+ = e;return ;void Pop(SqStack & S,SElemType &e)if = retur n ;return ;int judgePrecede nce(char a)int i = 7;switch(a)case '+': i =0; break;case '-': i =1; break;case '*': i =:2; break;case '/': i =3; brea

21、k;case '(': i =4; break;case ')': i =5; break;case '#': i =6; break;return i;int Precede nce(char a,char b)int i,j;i = judgePrecede nce(a);j = judgePrecede nce(b); int Pre77 = 1,1,-1,-1,-1,1,1,1,1,-1,-1,-1,1,1, 1,1,1,1,-1,1,1,1,1,1,1,-1,1,1,-1,-1,-1,-1,-1,0,-3,1,1,1,1,-1,1,1,

22、-1,-1,-1,-1,-1,-2,0;if(Preij = 1)return 1;else if(Preij = -1)return -1;else if(Preij = -2)return -2;else if(Preij = -3)return -3;elsereturn 0;int Operate。nt a,char b,i nt c)switch(b)case '+': retur n a+c; break;case '-': retur n a-c; break;case '*': retur n a*c; break;case &#

23、39;/':if(c = 0)return 1;elsereturn a/c;break;return 0;int pan dua n( char c) int i = 0;if(judgePrecede nce(c) != 7)i = 1;return i;void Yun sua n()SqStack A,B;int a,b,e;char c,d100;Ini tStack(A);Ini tStack(B);push(B, #);c = getchar();int i = 1;while(c !='#' | GetTop(B)!='#')int t

24、= 0;if(i = 1 && judgePrecede nce(c) != 7)if(judgePrecede nce(c) = 4)push(B,c);c = getchar();/+i; elsecout<<"第 1 位輸入"<<c<<"錯誤"<<endl;c = getchar();+i;while(pa ndua n(c)cout<<"第"<<i<<"位輸入"<<c<<"錯

25、誤"<<endl;c = getchar();+i;if(c >= 'O' && c <= 9)while(c >= '0' && c <= 9) dt+ = c;c = getchar();+i;/dt = '0'a = atoi(d); /字符型轉換為整形push(A,a);else if(judgePrecede nce(c) != 7)if(judgePrecede nce(c) = 4)cout<<"第"<<i<

26、;<"位輸入"<<c<<"錯誤"<<endl;c = getchar();+i；while(pa ndua n(c)/ /cout<<"第"<<i<<"位輸入"<<c<<"錯誤"<<endl;c = getchar();/+i; break; b = Precede nce(GetTop(B),c);switch(b)case 1:Pop(A,b);Pop(A,a);Pop(B,e);if(e = '/' && b = 0)cout<<"第"<<(i-1)<<"位非法輸入，除數(shù)