數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)3后綴表達(dá)式求值

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

2、及運(yùn)行結(jié)果用抓圖的形式粘貼到實(shí)驗(yàn)報(bào)告上)o(5)本程序調(diào)試通過(guò)以后，添加到原教材驗(yàn)證性實(shí)驗(yàn)3的菜單中去.4、實(shí)驗(yàn)步驟與源程序?qū)嶒?yàn)步驟我先從具體的問(wèn)題中抽象出適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)出相應(yīng)的算法，其中，需要設(shè)計(jì)個(gè)函數(shù)來(lái)求后 綴衣達(dá)式，設(shè)計(jì)另外一個(gè)函數(shù)來(lái)求后綴衣達(dá)式的值，最后，編寫主函數(shù)，串接程序，并調(diào)試程序，得出實(shí)驗(yàn) 結(jié)果。源代碼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.) /求后綴表達(dá)式. 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：輸入為空格.則跳過(guò)expt=>一;ch=str i:whil

5、e (op. top !=-l)expltl=op. data lop. topj :一；op. top:expCt 0float cocnpvalue(char exp.)/后綴表達(dá)式求值 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:?衣達(dá)式中有除數(shù)為零.本次計(jì)算無(wú)效:" >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 請(qǐng)輸入一個(gè)算術(shù)表達(dá)式："):printfCq 提示：操作數(shù)的范圍是“I ”運(yùn)算符只含+,*./和括號(hào)，中間不可以有空格B)： 2CT5(5tr)； prin原算木表這式為：%sn*» str);:ran 5 (str, exps);m-f(飛其后綴衣達(dá)式為, '>8 n" , exps)

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