線性表及其應用

本文格式為Word版，下載可任意編輯——線性表及其應用

哈爾濱工業(yè)大學計算機科學與技術(shù)學院

試驗報告

課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程類型：必修

試驗項目名稱：線性表及其應用試驗題目：算術(shù)表達式求值

班級：1003201

學號：姓名：

設計成績報告成績指導老師一、試驗目的

1.把握棧的數(shù)據(jù)結(jié)構(gòu)與基本操作2.了解什么是中綴表達式和后綴表達

3.了解并把握中綴表達式轉(zhuǎn)為后綴表達式的方法4.把握使用棧結(jié)構(gòu)求解后綴表達式的求值方法5.提高利用計算機分析和解決繁雜實際問題的能力二、試驗要求及試驗環(huán)境1.試驗要求：

(1)從鍵盤輸入任意一個語法正確的（中綴）表達式，顯示并保存該表達式。

(2)利用棧結(jié)構(gòu)，把上述（中綴）表達式轉(zhuǎn)換成后綴表達式，并顯示棧的狀態(tài)變化過程和所得到的后綴表達式。

(3)利用棧結(jié)構(gòu)，對上述后綴表達式進行求值，并顯示棧的狀態(tài)變化過程和最終結(jié)果。

2.試驗環(huán)境：

Windows7操作系統(tǒng)DevcC++編譯器

三、設計思想（本程序中的用到的所有數(shù)據(jù)類型的定義，主程序的流程圖及各程序模塊之間的調(diào)用關(guān)系）

程序中用到的數(shù)據(jù)類型的定義：

charstring1[100];//存放表達式

structStack{//定義一個棧chardata[maxlength];inttop;

};

typedefstructStackstack1;

stack1output1;//存放操作符

stackoutput1;//存放后綴表達式的數(shù)字的棧

主程序流程圖：

彈出棧內(nèi)所有元素存入結(jié)尾數(shù)組低直接壓入棧中開始輸入一個以字符串形式定義的運算式并保存至數(shù)組string1[100]中,聲明一個運算符棧用來存放運算符指針遍歷字符串數(shù)組高直接存入結(jié)尾數(shù)組中與棧頂運算符比較直接壓入棧中并在結(jié)尾數(shù)組中存入空格彈出棧內(nèi)與之匹配的（前的所有運算符并存結(jié)尾數(shù)組中為運算符存入空格為數(shù)字判斷字符串數(shù)組每一個單元的內(nèi)容為（存入空格為）

將棧內(nèi)元素全部存至結(jié)尾數(shù)組中彈出整型棧中的兩個元素進行相應的加減乘除運算，并將運算結(jié)果重新壓入棧中為運算符將空格之前到前一個空格之間的所有存入數(shù)字數(shù)組中的數(shù)字進行位數(shù)計算得到一個新的數(shù)字壓入棧中將字符型轉(zhuǎn)換為整型存入一個數(shù)字數(shù)組中去遍歷結(jié)尾數(shù)組中的每一個元素申請一個新的整型棧用于后綴表達式計算將后綴字符串和計算得到的結(jié)構(gòu)輸出判斷每一個元素的內(nèi)容為“〞為數(shù)字

終止各程序模塊之間的調(diào)用關(guān)系：

in