算法表達(dá)式語(yǔ)法檢查(數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì))

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院課程設(shè)計(jì)報(bào)告課 程 數(shù)據(jù)結(jié)構(gòu)題 目 算法表達(dá)式語(yǔ)法檢查年 級(jí) 2014專 業(yè) 軟件工程學(xué) 生 柳真學(xué) 號(hào) 201421092073指導(dǎo)教師 劉賽 2015年12 月20 日中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院本科課程設(shè)計(jì)任 務(wù) 書設(shè)計(jì)名稱： 算術(shù)表達(dá)式語(yǔ)法檢查指導(dǎo)教師： 下達(dá)時(shí)間： 2015-11-30 學(xué)生姓名： 學(xué) 號(hào)： 年級(jí)專業(yè)： 2014級(jí)軟件工程一、 課程設(shè)計(jì)的基本要求利用數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識(shí)完成一個(gè)具有一定難度的綜合設(shè)計(jì)題目，利用C/C+語(yǔ)言進(jìn)行程序設(shè)計(jì)，并規(guī)范地完成課程設(shè)計(jì)報(bào)告。通過課程設(shè)計(jì)，鞏固和加深對(duì)線性表、棧、隊(duì)列、字符串、樹、圖、查找、排

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

3、和計(jì)算機(jī)的對(duì)話方式進(jìn)行，利用文件進(jìn)行數(shù)據(jù)的提取與存儲(chǔ)。4、 程序算法說明清晰，理論分析與計(jì)算正確，運(yùn)行情況良好，實(shí)驗(yàn)測(cè)試數(shù)據(jù)無誤，容錯(cuò)性強(qiáng)（能對(duì)錯(cuò)誤輸入進(jìn)行判斷控制）。5、 編程風(fēng)格良好（包括縮進(jìn)、空行、適當(dāng)注釋、變量名和函數(shù)名見名知意，程序容易閱讀等）；6、 寫出規(guī)范的課程設(shè)計(jì)報(bào)告，具體要求見相關(guān)說明文檔。二、 課程設(shè)計(jì)的主要內(nèi)容 題目描述：算術(shù)表達(dá)式語(yǔ)法檢查。功能要求及說明：（1）鍵盤讀入一個(gè)四則運(yùn)算算術(shù)表達(dá)式，對(duì)其進(jìn)行語(yǔ)法檢查；（2）算術(shù)表達(dá)式允許嵌套，如果出錯(cuò)，指出出錯(cuò)位置；（3）不需要計(jì)算結(jié)果；（4）盡量不使用棧。三、 課程設(shè)計(jì)的進(jìn)程安排12015年11月30日：布置并下達(dá)課程設(shè)計(jì)題

4、目。22015年12月7日之前：聯(lián)系指導(dǎo)教師，理解課程設(shè)計(jì)題目及相關(guān)要求，查閱相關(guān)資料，進(jìn)行課程設(shè)計(jì)（地點(diǎn)：9-204，9-206）。32015年12月7日至12月31日（第15周-第18周）：課程設(shè)計(jì)源程序的調(diào)試、修改與檢查，書寫課程設(shè)計(jì)報(bào)告（地點(diǎn)：計(jì)算機(jī)科學(xué)學(xué)院實(shí)驗(yàn)機(jī)房）。42016年12月31日之前：上交、檢查設(shè)計(jì)報(bào)告（地點(diǎn)：計(jì)算機(jī)科學(xué)學(xué)院實(shí)驗(yàn)機(jī)房）。指導(dǎo)教師：2015年 11月20日算術(shù)表達(dá)式語(yǔ)法檢查一 目的根據(jù)課題要求，完成算法表達(dá)式語(yǔ)法檢查。具體完成以下四點(diǎn)要求：（1）鍵盤讀入一個(gè)四則運(yùn)算算術(shù)表達(dá)式，對(duì)其進(jìn)行語(yǔ)法檢查；（2）算術(shù)表達(dá)式允許嵌套，如果出錯(cuò)，指出出錯(cuò)位置；（3）不需要計(jì)

5、算結(jié)果；（4）盡量不使用棧。二 需求分析1、選擇存放算術(shù)表達(dá)式的數(shù)據(jù)結(jié)構(gòu)本次課設(shè)，我選擇了本學(xué)期數(shù)據(jù)結(jié)構(gòu)中所學(xué)的棧來實(shí)現(xiàn)算術(shù)表達(dá)式中的字符存放。2、運(yùn)算符優(yōu)先級(jí)劃分一個(gè)完整的算術(shù)表達(dá)式中包含+、-、*、/、（、）六種運(yùn)算符，當(dāng)遇到這些字符時(shí)要確定其優(yōu)先級(jí)的高低，并依次存放進(jìn)棧或者出棧。并且還可以進(jìn)行發(fā)現(xiàn)輸入錯(cuò)誤提示判斷，達(dá)到課題中相關(guān)要求。三 概要設(shè)計(jì)1、運(yùn)算符優(yōu)先級(jí)等級(jí)劃分表+-*/()#+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代表?xiàng)Ｖ羞\(yùn)算符出棧，進(jìn)行運(yùn)算；0代表?xiàng)Ｖ羞\(yùn)

6、算符（或#）出棧；-1代表當(dāng)前運(yùn)算符進(jìn)棧；-2代表當(dāng)前輸入）錯(cuò)誤；-3代表算術(shù)表達(dá)式末尾少輸入）。2、程序流程圖開始輸入一個(gè)算術(shù)表達(dá)式c!=#| GetTob(B)!=#定義一個(gè)棧A，用來存放數(shù)字；定義一個(gè)棧B用來存放運(yùn)算符從表達(dá)式首字符開始，獲取一個(gè)字符存放到c中，開始依次檢查定義一個(gè)字符變量c，一個(gè)字符數(shù)組d100如果是(進(jìn)棧，否則報(bào)錯(cuò)檢查下一個(gè)字符首字符是運(yùn)算符字符是運(yùn)算符字符是數(shù)字是是否否是是結(jié)束否字符是數(shù)字將字符串?dāng)?shù)組d100轉(zhuǎn)化為數(shù)字，存入棧A字符是運(yùn)算符字符是(字符是運(yùn)算符檢查下一個(gè)字符報(bào)錯(cuò)判斷運(yùn)算符優(yōu)先級(jí)，將結(jié)果放入b中跳出本次循環(huán)，進(jìn)行下一次循環(huán)檢查下一個(gè)字符數(shù)字放入字符數(shù)組

7、d100否是否是是是否否否b = 1A中最后進(jìn)棧的兩個(gè)數(shù)出棧，B中最后進(jìn)棧的運(yùn)算符出棧，進(jìn)行運(yùn)算，運(yùn)算結(jié)果存入棧A進(jìn)行下一個(gè)字符檢查，若字符是），報(bào)錯(cuò)。檢查下一個(gè)字符b = -1字符是(字符是運(yùn)算符運(yùn)算符進(jìn)棧B是跳出本次循環(huán)，進(jìn)行下一次循環(huán)否是運(yùn)算符進(jìn)棧B是進(jìn)行下一個(gè)字符檢查否報(bào)錯(cuò)是跳出本次循環(huán)，進(jìn)行下一次循環(huán)否否否報(bào)錯(cuò)，輸入非法字符檢查下一個(gè)字符結(jié)束b = 0B中運(yùn)算符出棧跳出本次循環(huán)，進(jìn)行下一次循環(huán)進(jìn)行下一個(gè)字符檢查是b = -2否報(bào)錯(cuò)，輸入)錯(cuò)誤進(jìn)行下一個(gè)字符檢查跳出本次循環(huán)，進(jìn)行下一次循環(huán)是否跳出本次循環(huán)，進(jìn)行下一次循環(huán)否b = -3B中運(yùn)算符出棧，并報(bào)錯(cuò)。第i位少輸入)跳出本次循環(huán)，

8、進(jìn)行下一次循環(huán)是否四 詳細(xì)設(shè)計(jì)1、棧的結(jié)構(gòu)及相關(guān)功能函數(shù)構(gòu)造偽代碼typedef int SElemType;const int STACK_INIT_SIZE = 100; /存儲(chǔ)空間初始分配量const int STACKINCREMENT = 10; /存儲(chǔ)空間分配增量typedef structSElemType *base; / 棧底指針，在棧構(gòu)造前和銷毀后，其值均為空SElemType *top; /棧頂指針int stacksize; /當(dāng)前已分配的存儲(chǔ)空間SqStack;/構(gòu)造一個(gè)空棧void InitStack(SqStack &S);/若棧不為空，返回棧頂元素值SE

9、lemType GetTop(SqStack & S);/插入元素e為棧的新棧頂元素void push(SqStack &S,SElemType e);/用e返回棧頂元素，并刪除棧頂元素void Pop(SqStack &S,SElemType &e);2、實(shí)現(xiàn)表達(dá)式語(yǔ)法檢查功能函數(shù)構(gòu)造偽代碼/判定輸入的運(yùn)算符，并分類標(biāo)記int judgePrecedence(char a)int i = 7;switch(a) case '+': i = 0; break; case '-': i = 1; break; case '*

10、': i = 2; break; case '/': i = 3; break; case '(': i = 4; break; case ')': i = 5; break; case '#': i = 6; break; return i;/比較運(yùn)算符的優(yōu)先級(jí)，并標(biāo)記分類int Precedence(char a,char b) 根據(jù)judgePrecedence（）函數(shù)確定a、b的運(yùn)算符種類，然后構(gòu)建一個(gè)7*7的二維數(shù)組表，依次填入優(yōu)先級(jí)，并返回相應(yīng)優(yōu)先等級(jí)。具體表格信息見概要設(shè)計(jì)中運(yùn)算符優(yōu)先等級(jí)劃分表。/執(zhí)行運(yùn)算i

11、nt Operate(int a,char b,int c) 其中a、c是數(shù)字，b是運(yùn)算符（+、-、*、/），實(shí)現(xiàn)具體運(yùn)算操作，并返回運(yùn)算結(jié)果值。/判斷c是否是運(yùn)算符int panduan(char c) 根據(jù)judgePrecedence（）函數(shù)，判斷c是否是運(yùn)算符，如果是怎返回1，否則返回0。/具體應(yīng)用操作void Yunsuan() SqStack A,B; /創(chuàng)建棧A、B push(B,'#'); /棧B中棧底存入# c = getchar(); /獲取算術(shù)表達(dá)式中字符 int i = 1; while(c !='#' | GetTop(B)!='

12、;#') if(i = 1 && judgePrecedence(c) != 7) 首字符是運(yùn)算符，報(bào)錯(cuò)； if(c >= '0' && c <= '9') 字符是數(shù)字，存放在數(shù)組d100中，后轉(zhuǎn)化為數(shù)字存入棧A中； else if(judgePrecedence(c) != 7) 字符是運(yùn)算符，進(jìn)行判斷，有錯(cuò)則報(bào)錯(cuò)，沒有則進(jìn)棧B； else 報(bào)錯(cuò)，輸入非法字符。五 調(diào)試分析1、算法邏輯問題及輸出錯(cuò)誤檢查一個(gè)算術(shù)表達(dá)式錯(cuò)誤時(shí)，要具體要第幾位以及是哪些錯(cuò)誤，在剛開始的檢查功能檢查設(shè)計(jì)的時(shí)候，我的代碼只能檢查到+、

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

14、)(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、具體運(yùn)算檢查分析結(jié)果截圖圖一：上圖一是設(shè)計(jì)輸入的算術(shù)表達(dá)式(1)(4)運(yùn)行結(jié)果截圖；圖二：上圖二是設(shè)計(jì)輸入的算術(shù)表達(dá)式(5)(8)運(yùn)行結(jié)果截圖；圖三：上圖三是輸入設(shè)計(jì)的算術(shù)表達(dá)式(9)(10)運(yùn)行結(jié)果截圖。七 用戶使用說明1、輸入規(guī)則輸入一個(gè)算術(shù)表達(dá)式，其中對(duì)應(yīng)的運(yùn)算符是+、-、*、/、(、)表達(dá)的意思是加、減、乘、除、順括號(hào)、反括號(hào)。 要求輸入一個(gè)算術(shù)表達(dá)式完畢后，在輸入一個(gè)#結(jié)束輸入，最后按enter鍵即可

15、得到算術(shù)表達(dá)式語(yǔ)法檢查結(jié)果。八 課程設(shè)計(jì)總結(jié)在本次課程設(shè)計(jì)實(shí)施的過程中，遇到了很多問題，當(dāng)然收獲也很多。起初，讓我感覺很難的地方在于如何確定算術(shù)表達(dá)式錯(cuò)誤的位置以及有哪些錯(cuò)誤要確定。在此過程中，我用了一個(gè)整形變量來計(jì)算依次檢查的字符數(shù)，來確定錯(cuò)誤的具體位置。其中錯(cuò)誤的類型要分類進(jìn)行查找，在算法實(shí)施之前我把錯(cuò)誤類型進(jìn)行分類，并初步畫出算法的程序流程圖，不斷反復(fù)推敲和檢查，從中也發(fā)現(xiàn)了我很多邏輯上的錯(cuò)誤。通過不斷修改和測(cè)試，也讓我設(shè)計(jì)的核心功能函數(shù)不斷完善，最終達(dá)到課題的要求。附具體源碼：#include<iostream>#include<cstdio>#include&

16、lt;cstdlib>using namespace std;typedef int SElemType;const int STACK_INIT_SIZE = 100; /存儲(chǔ)空間初始分配量const int STACKINCREMENT = 10; /存儲(chǔ)空間分配增量typedef structSElemType *base; / 棧底指針，在棧構(gòu)造前和銷毀后，其值均為空SElemType *top; /棧頂指針int stacksize; /當(dāng)前已分配的存儲(chǔ)空間SqStack;/構(gòu)造一個(gè)空棧void InitStack(SqStack &S);/若棧不為空，返回棧頂元素值S

17、ElemType GetTop(SqStack & S);/插入元素e為棧的新棧頂元素void push(SqStack &S,SElemType e);/用e返回棧頂元素，并刪除棧頂元素void Pop(SqStack &S,SElemType &e);/判定輸入的運(yùn)算符，并分類標(biāo)記int judgePrecedence(char a);/比較運(yùn)算符的優(yōu)先級(jí)，并標(biāo)記分類int Precedence(char a,char b);/執(zhí)行運(yùn)算int Operate(int a,char b,int c);/判斷c是否是運(yùn)算符int panduan(char c);

18、/具體應(yīng)用操作void Yunsuan();int main() while(1) cout<<"請(qǐng)輸入算術(shù)表達(dá)式（按#結(jié)束）：" Yunsuan(); /* cout<<"繼續(xù)輸入算術(shù)表達(dá)式請(qǐng)輸入$，退出請(qǐng)輸入#："<<endl; char i; cin>>i; if(i = '#' ) break;*/ return 0;void InitStack(SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SEle

19、mType);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return ;SElemType GetTop(SqStack & S)if(S.top = S.base) return 0;return *(S.top-1);void push(SqStack &S,SElemType e)if(S.top - S.base >= S.stacksize)S.base = (SElemType * )realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SElemType)

20、;if(!S.base) exit(0);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;return ;void Pop(SqStack &S,SElemType &e)if(S.top = S.base) return ;e = * -S.top;return ;int judgePrecedence(char a)int i = 7;switch(a) case '+': i = 0; break; case '-': i = 1; break;

21、case '*': i = 2; break; case '/': i = 3; break; case '(': i = 4; break; case ')': i = 5; break; case '#': i = 6; break; return i;int Precedence(char a,char b)int i,j;i = judgePrecedence(a);j = judgePrecedence(b);int Pre77 = 1,1,-1,-1,-1,1,1,1,1,-1,-1,-1,1,1,1,

22、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,-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(int a,char b,int c)switch(b) case '+': return a+c; break; case '-':

23、 return a-c; break; case '*': return a*c; break; case '/': if(c = 0) return 1; else return a/c; break; return 0;int panduan(char c)int i = 0;if(judgePrecedence(c) != 7)i = 1;return i;void Yunsuan()SqStack A,B;int a,b,e;char c,d100;InitStack(A);InitStack(B);push(B,'#');c = get

24、char();int i = 1;while(c !='#' | GetTop(B)!='#')int t = 0; if(i = 1 && judgePrecedence(c) != 7) if(judgePrecedence(c) = 4) push(B,c); c = getchar();+i;else cout<<"第1位輸入"<<c<<"錯(cuò)誤"<<endl; c = getchar(); +i; while(panduan(c) cout<&l

25、t;"第"<<i<<"位輸入"<<c<<"錯(cuò)誤"<<endl; c = getchar(); +i;if(c >= '0' && c <= '9')while(c >= '0' && c <= '9') dt+ = c;c = getchar();+i;dt = '0'a = atoi(d); /字符型轉(zhuǎn)換為整形 push(A,a);else

26、 if(judgePrecedence(c) != 7)if(judgePrecedence(c) = 4)cout<<"第"<<i<<"位輸入"<<c<<"錯(cuò)誤"<<endl;c = getchar();+i;while(panduan(c)cout<<"第"<<i<<"位輸入"<<c<<"錯(cuò)誤"<<endl;c = getchar();+i;break; b = Precedence(GetTop(B),c);switch(b)case 1: Pop(A,b);Pop(A,a);Pop(B,e); if(e = '/' && b = 0)cout<<"第"<<(i-1)<<"位非法輸入，除數(shù)不能為0！"<<endl;pus