算術(shù)表達(dá)式求值-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、word word 文檔 可自由復(fù)制編輯清華大學(xué)數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告（ 20 -20 學(xué)年 第 學(xué)期）報(bào)告題目：算術(shù)表達(dá)式求值任課老師： TOC o 1-5 h z 專業(yè)：學(xué)號(hào)：姓名：0一 年 月 日摘要：現(xiàn)代科學(xué)技術(shù)高速發(fā)展，各種高科技產(chǎn)品頻頻問(wèn)世，而各種技術(shù)的基礎(chǔ)都離不開(kāi)基本的表達(dá)式求值，它雖然簡(jiǎn)單，但卻是任何復(fù)雜系統(tǒng)的基本執(zhí)行操作。 棧是一種重要的線性結(jié)構(gòu)，從數(shù)據(jù)結(jié)構(gòu)的角度看，它是一種特殊的線性表，具有先入先出的特點(diǎn)。而算符優(yōu)先法的設(shè)計(jì)恰巧符合先入先出的思想。故我們基于棧這種數(shù)據(jù)結(jié)構(gòu)，利用算符優(yōu)先法，來(lái)實(shí)現(xiàn)簡(jiǎn)單算術(shù)表達(dá)式的求值。關(guān)鍵字： 算符優(yōu)先法；算術(shù)表達(dá)式；數(shù)據(jù)結(jié)構(gòu)；棧一、課題概述1

2、、問(wèn)題描述一個(gè)算術(shù)表達(dá)式是由運(yùn)算數(shù)、運(yùn)算符、界限符組成。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含有加“+”、減“-”、乘“*”、除“/ ”四種二元運(yùn)算符，界限符有左括號(hào)“ （” 、右括號(hào)“） ”和表達(dá)式起始、結(jié)束符“#”。利用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值。2、設(shè)計(jì)目的通過(guò)該算法的設(shè)計(jì)思想，熟悉棧的特點(diǎn)和應(yīng)用方法；通過(guò)對(duì)算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的算法執(zhí)行過(guò)程的演示，理解在執(zhí)行相應(yīng)棧的操作時(shí)的變化過(guò)程。通過(guò)程序設(shè)計(jì)，進(jìn)一步熟悉棧的基本運(yùn)算函數(shù)；通過(guò)自己動(dòng)手實(shí)現(xiàn)算法，加強(qiáng)從偽碼算法到C語(yǔ)言程序的實(shí)現(xiàn)能力。3、基本要求：1）使用棧的順序存儲(chǔ)表示方式；2）使用算符優(yōu)先法；3）用C語(yǔ)言實(shí)現(xiàn)；4）從鍵盤(pán)輸入一個(gè)符合要

3、求的算術(shù)表達(dá)式，輸出正確的結(jié)果。、編程實(shí)現(xiàn)平臺(tái)Microsoft Visual C+ 6.0二、設(shè)計(jì)思路及采取方案1、設(shè)計(jì)思路：為了實(shí)現(xiàn)算符優(yōu)先法，可以使用兩個(gè)工作棧。一個(gè)稱做OPTR，用以寄存運(yùn)word 文檔 可自由復(fù)制編輯word word 文檔 可自由復(fù)制編輯算符；另一個(gè)稱做OPN，用以寄存操作數(shù)或運(yùn)算結(jié)果。D算法的基本思想是：( 1)首先置操作數(shù)棧為空棧，表達(dá)式起始符“#”作為運(yùn)算符棧的棧底元素；( 2)依次讀入表達(dá)式中每個(gè)字符，若是操作數(shù)則進(jìn)入OPND棧，若是運(yùn)算符則和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個(gè)表達(dá)式求值完畢(即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為“#

4、”) 。算法中還調(diào)用了兩個(gè)函數(shù)。其中函數(shù)Precede是判定運(yùn)算符棧頂運(yùn)算符1與讀入的運(yùn)算符2 之間優(yōu)先關(guān)系的函數(shù)；函數(shù)Operate 為進(jìn)行二元運(yùn)算a b 的函數(shù)，如果是編譯表達(dá)式，則產(chǎn)生這個(gè)運(yùn)算的一組相應(yīng)指令并返回存放結(jié)果的中間變量名；如果是解釋執(zhí)行表達(dá)式，則直接進(jìn)行該運(yùn)算，并返回運(yùn)算結(jié)果。2、方案設(shè)計(jì)( 1)抽象數(shù)據(jù)類(lèi)型定義ADT Stack數(shù)據(jù)對(duì)象：D= ai | ai ElemSet,i=1,2, ,n, n 0數(shù)據(jù)對(duì)象：R1= | ai , ai 1 D， i=2, ,n約定 an 端為棧頂，ai 端為棧底。基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。GetTop

5、(S)初始條件：棧S已存在。操作結(jié)果：用P返回S的棧頂元素。Push(&S, e)初始條件：棧S已存在。操作結(jié)果：插入元素e 為新的棧頂元素。Pop(&S, e)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素，并用e 返回其值。Precede( c1 , c2)初始條件：c1 , c2為運(yùn)算符。操作結(jié)果：判斷運(yùn)算符優(yōu)先權(quán)，返回表示優(yōu)先權(quán)高低關(guān)系的“”的字符。Operate（a, OP, b）初始條件：a, b 為整數(shù)，OP為運(yùn)算符。操作結(jié)果：a 與 b 進(jìn)行運(yùn)算，OP為二元運(yùn)算符，返回其值。ADT Stack（ 2）符號(hào)之間的優(yōu)先權(quán)關(guān)系比較1 2 ：1 的優(yōu)先權(quán)高于221+-*/()#+-*

6、/(#=（ 3）順序棧的定義typedef structSElemType *base;SElemType *top;int stacksize;SqStack;( 4)調(diào)用函數(shù)：構(gòu)造空棧用 e 構(gòu)造空棧用 e 返回棧頂元素/ 插入 e為新的棧頂元素SElemType GetTop(SqStack *S)/SElemType Push(SqStack *S, SElemType e)SElemType Pop(SqStack *S) int jiancha1(char e) / void jiancha2(char e) /SElemType Precede(char g, char h)/刪

7、除棧頂元素判斷/刪除棧頂元素判斷e 是運(yùn)算符還是運(yùn)算數(shù)判斷e 是否為合法的運(yùn)算符或運(yùn)算數(shù)/ 優(yōu)先權(quán)比較/ 返回二元運(yùn)算結(jié)果三、實(shí)驗(yàn)結(jié)果測(cè)試表達(dá)式及對(duì)應(yīng)運(yùn)行結(jié)果2、“（ 7-5） *3#” 結(jié)果為 63、2、“（ 7-5） *3#” 結(jié)果為 63、“ 8/4# ” 結(jié)果為 2.、 算符優(yōu)先法是教材上有關(guān)棧的應(yīng)用的一個(gè)具體實(shí)例，考慮到算符優(yōu)先法中對(duì)于運(yùn)算符的操作是先入先出的，正好符合棧這種結(jié)構(gòu)的存儲(chǔ)使用規(guī)則，于是我們便可以利用棧來(lái)實(shí)現(xiàn)算法由于教材上給出的存儲(chǔ)結(jié)構(gòu)定義、函數(shù)等都是偽碼，不是可執(zhí)行的程序代碼，故需要從程序語(yǔ)言（C 語(yǔ)言）角度考慮，將偽碼轉(zhuǎn)換成程序代碼。而這是不是一個(gè)簡(jiǎn)單的工作。編寫(xiě)程序

8、的過(guò)程需要非常的小心仔細(xì)，任何一個(gè)細(xì)小的錯(cuò)誤，都會(huì)導(dǎo)致程序的運(yùn)行失敗。在寫(xiě)好程序第一次編譯時(shí)，我的程序出現(xiàn)了將近 80 條錯(cuò)誤， 經(jīng)過(guò)兩天的檢查、調(diào)試以及和同學(xué)的討論，我的程序才最終通過(guò)編譯，成功運(yùn)行。比如在定義字符常量時(shí)，#define STACK_INIT_SIZE1 00和 #define STACKINCREMENT 這兩個(gè)語(yǔ)句的句末是不能加分號(hào)的，這個(gè)問(wèn)題10我花了兩個(gè)多小時(shí)才發(fā)現(xiàn)。經(jīng)過(guò)自己動(dòng)手編寫(xiě)這個(gè)有關(guān)棧的程序，我發(fā)現(xiàn)自己對(duì)棧的理解更加完全、更加深刻了。對(duì)于棧的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、操作函數(shù)、應(yīng)用以及具體實(shí)現(xiàn)，我有一種豁然開(kāi)朗的感覺(jué)。 TOC o 1-5 h z 此算法只能進(jìn)行個(gè)位

9、數(shù)的加減乘除運(yùn)算，對(duì)兩位及以上數(shù)不能操作，。因此算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值存在很大的局限性。若要完善算術(shù)表達(dá)式求值，應(yīng)該完善算法，或者換用其它算法來(lái)實(shí)現(xiàn)。五、參考文獻(xiàn)1 】嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C 語(yǔ)言版）. 北京：清華大學(xué)出版社，20072】 李春葆 . 數(shù)據(jù)結(jié)構(gòu)教程（第 3 版） 上機(jī)實(shí)驗(yàn)指導(dǎo). 北京： 清華大學(xué)出版社，20093】譚浩強(qiáng). C 程序設(shè)計(jì)（第四版）. 北京：清華大學(xué)出版社六、附錄C語(yǔ)言程序代碼及部分注釋#include#include#define ERROR 0;#define STACKINITSIZE 100#define STACKINCREMENT 10in

10、t flag=0;/flag標(biāo)記輸入字符是否合法int flag=0;/flag標(biāo)記輸入字符是否合法typedef structfloat *base;float *top;int stacksize;typedef structfloat *base;float *top;int stacksize;SqStack; / typedef struct char *base;char *top;int stacksize;sqStack; /存放運(yùn)算數(shù)的棧的順序存儲(chǔ)表示存放運(yùn)算符的棧的順序存儲(chǔ)表示void InitStack(SqStack *S)/構(gòu)造空棧(運(yùn)算數(shù)棧)S-base=(floa

11、t*)malloc(STACK_INIT_SIZE)*sizeof(float);S-top=S-base;S-stacksize=STACK_INIT_SIZE;void initStack(sqStack *S)/構(gòu)造空棧(運(yùn)算符棧)S-base=(char*)malloc(STACK_INIT_SIZE)*sizeof(char);S-top=S-base;S-stacksize=STACK_INIT_SIZE;float GetTop(SqStack *S)/用 float GetTop(SqStack *S)/用 e 返回棧頂元素（運(yùn)算數(shù)）float e;if(S-top=S-bas

12、e) return ERROR;e=*(S-top-1);return e;用 e 返回棧頂元素（運(yùn)算符）用 e 返回棧頂元素（運(yùn)算符）char e;if(S-top=S-base) return ERROR;e=*(S-top-1);return e;float Push(SqStack *S,float e) / 插入 e 為新的棧頂元素(運(yùn)算數(shù))if(S-top-S-base=S-stacksize)S-base=(float*)realloc(S-base,(S-stacksize+STACKINCREMEN T)*sizeof(float);S-top=S-base+S-stacks

13、ize;S-stacksize+=STACKINCREMENT;*S-top+=e;return e;char push(sqStack *S,char e) / 插入 e 為新的棧頂元素(運(yùn)算符)if(S-top-S-base=S-stacksize)S-base=(char*)realloc(S-base,(S-stacksize+STACKINCREMENT )*sizeof(char);S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;*(S-top)=e;(S-top)+;return e;float Pop(SqStack *

14、S)/刪除棧頂元素( 運(yùn)算數(shù) )float e;if(S-top=S-base) return ERROR;(S-top)-;e=*(S-top);return e;char pop(sqStack *S)/刪除棧頂元素( 運(yùn)算符 )char e;if(S-top=S-base) return ERROR;(S-top)-;e=*(S-top);return e;int jiancha1(char e) /判斷 e 是運(yùn)算符還是運(yùn)算數(shù)if(e!=+&e!=-&e!=*&e!=/&e!=(&e!=)&e!=#)return 1;else return 0;void jiancha2(char e

15、) /判斷 e 是否為合法的運(yùn)算符或運(yùn)算數(shù)if(e=48|e=49|e=50|e=51|e=52|e=53|e=54|e=55|e=56|e=57) flag=1;elseif(e=+|e=-|e=*|e=/|e=(|e=)|e=#)flag=1;else flag=0;char Precede(char p,char q) /優(yōu)先級(jí)比較函數(shù)switch(p)case+:if(q=*)|(q=/)|(q=()return;break;case-:if(q=*)|(q=/)|(q=()return;break; case*:if(q=() return ;break;case/:if(q=()

16、return ;break;case(:if(q=) return =; else if(q=#) return ;else return ;break;case#:if(q=#) return =; else if(q=) return ;else return ;break;default: printf( 你的輸入非法n);float Operate(float s,char yunsuanfu,float t) /二元運(yùn)算操作word 文檔 可自由復(fù)制編輯word word 文檔 可自由復(fù)制編輯float r;switch(yunsuanfu)case+:r=s+t;break;cas

17、e-:r=s-t;break;case*:r=s*t;break;case/:if(t!=0)r=s/t;else printf(分母不能為零！);break;default:printf(Sorry ，您的輸入有誤！);return r;void main() /主函數(shù)部分char c,x,theta;float a,b;sqStack OPTR;SqStack OPND;initStack(&OPTR);push(&OPTR,#);InitStack(&OPND);printf( 輸入一個(gè)以“#”結(jié)束的算數(shù)表達(dá)式:nn);c=getchar();jiancha2(c);while(flag&(c!=#|getTop(&OPTR)!=#)if(jiancha1(c)float cc;