算術(shù)表達式求值-數(shù)據(jù)結(jié)構(gòu)實驗報告

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

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

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

4、”) 。算法中還調(diào)用了兩個函數(shù)。其中函數(shù)Precede是判定運算符棧頂運算符1與讀入的運算符2 之間優(yōu)先關(guān)系的函數(shù)；函數(shù)Operate 為進行二元運算a b 的函數(shù)，如果是編譯表達式，則產(chǎn)生這個運算的一組相應(yīng)指令并返回存放結(jié)果的中間變量名；如果是解釋執(zhí)行表達式，則直接進行該運算，并返回運算結(jié)果。2、方案設(shè)計( 1)抽象數(shù)據(jù)類型定義ADT Stack數(shù)據(jù)對象：D= ai | ai ElemSet,i=1,2, ,n, n 0數(shù)據(jù)對象：R1= | ai , ai 1 D， i=2, ,n約定 an 端為棧頂，ai 端為棧底。基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個空棧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為運算符。操作結(jié)果：判斷運算符優(yōu)先權(quán)，返回表示優(yōu)先權(quán)高低關(guān)系的“”的字符。Operate（a, OP, b）初始條件：a, b 為整數(shù)，OP為運算符。操作結(jié)果：a 與 b 進行運算，OP為二元運算符，返回其值。ADT Stack（ 2）符號之間的優(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 是運算符還是運算數(shù)判斷e 是否為合法的運算符或運算數(shù)/ 優(yōu)先權(quán)比較/ 返回二元運算結(jié)果三、實驗結(jié)果測試表達式及對應(yīng)運行結(jié)果2、“（ 7-5） *3#” 結(jié)果為 63、2、“（ 7-5） *3#” 結(jié)果為 63、“ 8/4# ” 結(jié)果為 2.、 算符優(yōu)先法是教材上有關(guān)棧的應(yīng)用的一個具體實例，考慮到算符優(yōu)先法中對于運算符的操作是先入先出的，正好符合棧這種結(jié)構(gòu)的存儲使用規(guī)則，于是我們便可以利用棧來實現(xiàn)算法由于教材上給出的存儲結(jié)構(gòu)定義、函數(shù)等都是偽碼，不是可執(zhí)行的程序代碼，故需要從程序語言（C 語言）角度考慮，將偽碼轉(zhuǎn)換成程序代碼。而這是不是一個簡單的工作。編寫程序

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

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

10、t flag=0;/flag標記輸入字符是否合法int flag=0;/flag標記輸入字符是否合法typedef structfloat *base;float *top;int stacksize;typedef structfloat *base;float *top;int stacksize;SqStack; / typedef struct char *base;char *top;int stacksize;sqStack; /存放運算數(shù)的棧的順序存儲表示存放運算符的棧的順序存儲表示void InitStack(SqStack *S)/構(gòu)造空棧(運算數(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)造空棧(運算符棧)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 返回棧頂元素（運算數(shù)）float e;if(S-top=S-bas

12、e) return ERROR;e=*(S-top-1);return e;用 e 返回棧頂元素（運算符）用 e 返回棧頂元素（運算符）char e;if(S-top=S-base) return ERROR;e=*(S-top-1);return e;float Push(SqStack *S,float e) / 插入 e 為新的棧頂元素(運算數(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 為新的棧頂元素(運算符)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)/刪除棧頂元素( 運算數(shù) )float e;if(S-top=S-base) return ERROR;(S-top)-;e=*(S-top);return e;char pop(sqStack *S)/刪除棧頂元素( 運算符 )char e;if(S-top=S-base) return ERROR;(S-top)-;e=*(S-top);return e;int jiancha1(char e) /判斷 e 是運算符還是運算數(shù)if(e!=+&e!=-&e!=*&e!=/&e!=(&e!=)&e!=#)return 1;else return 0;void jiancha2(char e

15、) /判斷 e 是否為合法的運算符或運算數(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)先級比較函數(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) /二元運算操作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( 輸入一個以“#”結(jié)束的算數(shù)表達式:nn);c=getchar();jiancha2(c);while(flag&(c!=#|getTop(&OPTR)!=#)if(jiancha1(c)float cc;