數(shù)據(jù)結構實驗3后綴表達式求值

1、1、實驗目的(1)掌握?！昂筮M先出”的特點：(2)掌握棧的典型應用一-后綴表達式求值。2、實驗內(nèi)容用鍵盤輸入個整數(shù)后綴式達式(操作數(shù)的范。9,運算符只含人_、含、1,而且中間不可(1)圍是以有空格)，使用循環(huán)程序從左向右讀入衣達式；如果讀入的是運算符，立即從操作數(shù)計算操作數(shù)運算的值，并將計算結果(2)如果讀入的是操作數(shù)，直接進入操作數(shù)棧;(3)棧取出所需的操作數(shù)，存回操作數(shù)棧：(4)檢驗程序運行結果。3、實驗要求(1)分析后綴表達式求值的算法思想，用c(CH)語言完成程序設計.(2)上機調(diào)試通過實驗程序。(3)給出具體的算法分析，包括時間復雜度和空間復雜度等。(4)撰寫實驗報告(把輸入實驗數(shù)據(jù)

2、及運行結果用抓圖的形式粘貼到實驗報告上)o(5)本程序調(diào)試通過以后，添加到原教材驗證性實驗3的菜單中去.4、實驗步驟與源程序實驗步驟我先從具體的問題中抽象出適當?shù)臄?shù)學模型，然后設計出相應的算法，其中，需要設計個函數(shù)來求后 綴衣達式，設計另外一個函數(shù)來求后綴衣達式的值，最后，編寫主函數(shù)，串接程序，并調(diào)試程序，得出實驗 結果。源代碼sin clude<stdio. h> typed" struct *. char data.Xajjle n:int top:;opstack;typed" struct (float data.Xaxle n;int top:stac

3、k：void tran s (char str., char exp.) /求后綴表達式. ops tack op:char ch:op. top;T;ch=stri:while (ch!=> 0*)(switch (ch)caseop. op*:op. data .op. top.=ch;break:case )wnile (op. data.op. top !=* (')expLtj=op. data.op. top.op.top:op. top:break:case + ：case 一wnile (op. top !=1 Ide op. data .op. top. !=*

4、 (* ):exp.T'=op. data.op. top.op.top:op. top-op. data.op. topj=ch;break:case* * ：casewhile (op. top= / I o> top二二才expLtj=op. data.op. top.op. top-tfop.op. data.op. topj=ch;break:， ， casebreak:default：while (ch>= 0> 曲 ch<= 9>>(expCt=ch：一；ch=stri：輸入為空格.則跳過expt=>一;ch=str i:whil

5、e (op. top !=-l)expltl=op. data lop. topj :一；op. top:expCt 0float cocnpvalue(char exp.)/后綴表達式求值 stack zz：float d;char ch:int t=0:st.top=-l;ch=expt:tfwhile(ch!=' 01) 5witch(ch)(皿'+'：st. catalst. top-ll=st. catalst. toaT：八.dataLst. top:st.top;break:casest. cata.st. top-1. =5t. data.st. top

6、-1.-st. datalst. top：;st.top;break:casest. catalst. top-ll=st. catalst. top-ll*zt. dataLst. top:st.top;break:casei£(zz. caxalzt. top!=0) st. datalst. top-ll=zt. datatst. top-11/st. dataLst. top：st.top:?衣達式中有除數(shù)為零.本次計算無效:" >break;default：d=0:while (ch) 0* 心 ch<= 9') d=10*dch-* 0* ：

7、ch=expt：tf | St. topi； st. dataLzt. top =d: | ch=expt;tf |ru:ur n st. data.st. top; * Avoid mai n()： char str n» exps n：prin tfn 請輸入一個算術表達式："):printfCq 提示：操作數(shù)的范圍是“I ”運算符只含+,*./和括號，中間不可以有空格B)： 2CT5(5tr)； prin原算木表這式為：%sn*» str);:ran 5 (str, exps);m-f(飛其后綴衣達式為, '>8 n" , exps)

8、;prin其運算的結果為：%enn*. compvalue (exps);* A5、測試數(shù)據(jù)與實驗結果(可以抓圖粘貼)請輸入盲個算術丟達甘二*一1一1'一提不I操祜藪的罪圍臭運算符只含和括號，中間不可以有空格7+12/6-1 *3*9原算術表達式為：7+12/6-1*3-9其后韁表達式為匕7 12 t 7 9 *4苴運算的結果為756、結果分析與實驗體會本次實驗是參考了范例程序，經(jīng)過自己的改寫，從而實現(xiàn)要求。先做簡單的輸出，步步的再做其它格 式的設置。在實驗的過程中，我加深了時后綴農(nóng)達式算法的理解，讀入操作數(shù)時，直接輸出到后綴表達式， 讀入運算符，則壓入運算符號棧，而且，若后進的運算符優(yōu)先級高與先進的，則繼續(xù)進棧，若后進的運算符 優(yōu)先級不高于先進的，則將運算符號棧內(nèi)高于或等于后進運算符級別的運算符依次彈出并輸出到后綴表達 式，刻于括號，遇到開括號就進棧，遇到閉括號，則把窕近的開括號以及其后進棧的運算符依次彈出，并輸 出到后綴農(nóng)達式，