實(shí)驗(yàn)五 中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式算法(昆工版本)

1、昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告（ 2013 2014 學(xué)年第三學(xué)期 ）課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu) 開(kāi)課實(shí)驗(yàn)室：信自樓444 2013年11月12日年級(jí)、專(zhuān)業(yè)、班計(jì)科122班學(xué)號(hào)201210405204姓名鄒華宇成績(jī)實(shí)驗(yàn)項(xiàng)目名稱(chēng)中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式算法及后綴表達(dá)式計(jì)算算法的實(shí)現(xiàn)指導(dǎo)教師胡守成教師評(píng)語(yǔ) 教師簽名： 年 月 日注：報(bào)告內(nèi)容按實(shí)驗(yàn)須知中七點(diǎn)要求進(jìn)行。一、實(shí)驗(yàn)?zāi)康暮鸵蠼Y(jié)合堆棧入棧出棧的特點(diǎn)解決實(shí)際問(wèn)題。輸入一個(gè)含+、-、*、/、正整數(shù)和圓括號(hào)的合法的中綴表示的算術(shù)表達(dá)式，輸出轉(zhuǎn)化得到的后綴表達(dá)式，計(jì)算該表達(dá)式的運(yùn)算結(jié)果。調(diào)用直接計(jì)算的函數(shù)返回計(jì)算結(jié)果后綴表達(dá)式的計(jì)算調(diào)用函數(shù)

2、得到后綴表達(dá)式無(wú)錯(cuò)調(diào)用容錯(cuò)函數(shù)存在錯(cuò)誤 報(bào)錯(cuò)并結(jié)束得到用戶(hù)輸入的中綴表達(dá)式二、算法思想三、所用儀器、材料（設(shè)備名稱(chēng)、型號(hào)、規(guī)格等）聯(lián)想計(jì)算機(jī)一臺(tái)Microsoft Visual c+ 6.0四、程序源代碼#include<stdio.h> /*導(dǎo)入需要用到的各種包*/#include<stdlib.h>#include<string.h>typedef struct /*定義結(jié)構(gòu)體用來(lái)存儲(chǔ)操作符*/ char op; /*存儲(chǔ)字符*/ int level; /*存儲(chǔ)優(yōu)先級(jí)*/OpNode;typedef struct OpNode op100; int to

3、p; int size; /*表示棧內(nèi)元素的個(gè)數(shù)*/ stack; /*定義符號(hào)棧*/void init(stack *st) /*初始化棧*/ st->size=0; st->top=0;OpNode pop(stack *a) /* 出棧*/ if (a->size=0) /*如果棧為空結(jié)束操作*/ exit(-1); a->size-; return a->op-(a->top); /*取出棧頂元素*/void push(stack *a,OpNode op) /*入棧函數(shù)*/ a->size+; a->op(a->top)+=op;

4、OpNode top(stack *a) /*觀察棧頂函數(shù)*/ if (a->size=0) /*如果棧為空結(jié)束操作*/ printf("stack is emptyn"); exit(-1); return a->op(a->top)-1; /*只得到棧頂?shù)闹刀怀鰲?/typedef struct /*定義數(shù)值棧*/ double num100; int top; /*棧頂指針*/ int size; numstack;void init2(numstack *st) /*初始化數(shù)值棧*/ st->size=0; st->top=0;dou

5、ble pop2(numstack *a) /*數(shù)值棧出棧*/ if (a->size=0) /*出棧前的判空*/ exit(-1); a->size-; return a->num-(a->top); /*得到棧頂?shù)闹?/void push2(numstack *a,double num) /*入棧*/ a->size+; a->num(a->top)+=num;void main() /*主函數(shù)*/ char ch='y' void change (char str,char exp); /*聲明要用到的各個(gè)函數(shù)*/ double

6、CalResult(char exp); /*聲明后綴表達(dá)式的計(jì)算函數(shù)*/ double Directcalresult(char str); int check(char str,char chestr100); char str100,exp100,chestr100; /*str存儲(chǔ)原算術(shù)表達(dá)式，exp存儲(chǔ)對(duì)應(yīng)的后綴表達(dá)式,chestr存儲(chǔ)容錯(cuò)字符''*/ do printf("算術(shù)表達(dá)式為:n"); gets(str); if(check(str,chestr) /*調(diào)用容錯(cuò)函數(shù)*/ printf("表達(dá)式錯(cuò)在：n"); prin

7、tf("%sn",str); printf(chestr); /*根據(jù)輸入情況指出錯(cuò)誤的地方*/ printf("n"); printf("Try agian<y/n>:"); while(ch=getchar(),ch!='n'&&ch!='y'); if(ch='y')system("pause");continue; if(ch='n') system("pause");exit(-1); chan

8、ge(str,exp); /*調(diào)用函數(shù)將中綴轉(zhuǎn)化為后綴*/ printf("后綴表達(dá)式為:%sn",exp); printf("運(yùn)算結(jié)果為： %fn",CalResult(exp); /*調(diào)用函數(shù)計(jì)算后綴表達(dá)式*/ printf("Try agian<y/n>:"); while(ch=getchar(),ch!='n'&&ch!='y'); system("pause"); while(ch!='n');void change (char

9、 str,char ch) /*將前綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式*/ int i=0; /*str的索引*/ int k=0; char c; /*字符串中取出的放在C中*/ stack st; /*定義符號(hào)棧*/ OpNode op; OpNode ops; init(&st); /*初始化符號(hào)棧*/ c=stri+; while (c!='0') /*對(duì)字符串進(jìn)行掃描*/ if ( (c>='0'&&c<='9')|c='.') /*如果字符為數(shù)字或小數(shù)點(diǎn)*/ while ( (c>=&#

10、39;0'&&c<='9')|c='.') chk+=c; /*將字符直接放入數(shù)組中*/ c=stri+; chk+='|' /*在其后面放入一個(gè)分隔符*/ if (c='(') /*如果字符是左括號(hào)*/ op.op='(' op.level=-1; /*定義其優(yōu)先級(jí)為-1*/ push(&st,op); /*將左括號(hào)直接入棧*/ if(c=')') /*如果字符為右括號(hào)*/ op=top(&st); /*首先觀察棧頂*/ while (st.size!

11、=0&&op.op!='(') /*如果不是左括號(hào)并且棧不為空*/ op=pop(&st); /*出棧并存入數(shù)組中*/ chk+=op.op; if (st.size>0) /*再次檢查棧是否為空，*/ op=top(&st); else break; /*為空就結(jié)束*/ pop(&st); /*去掉左括號(hào)*/ if (c='+'|c='-') /*如果是+-號(hào)*/ op.op=c; op.level=1; /*優(yōu)先級(jí)為1*/ if (st.size=0) push(&st,op); /*如果

12、此時(shí)棧為空直接入棧*/ else ops=top(&st); /*觀察棧頂*/ while (ops.level>=op.level) /*如果棧頂優(yōu)先級(jí)高*/ ops=pop(&st); chk+=ops.op; /*將棧頂元素取出存入數(shù)組中*/ if (st.size>0) ops=top(&st); /*進(jìn)行判空操作，棧為空結(jié)束*/ else break; push(&st,op); /*此時(shí)棧頂優(yōu)先級(jí)低，入棧*/ if(c='*'|c='/'|c='%') /*如果是進(jìn)行*/ op.op=c;

13、op.level=2; /*優(yōu)先級(jí)為1*/ if (st.size=0) push(&st,op); /*如果此時(shí)棧為空直接入棧*/ else ops=top(&st); /*觀察棧頂*/ while (ops.level>=op.level) /*如果棧頂優(yōu)先級(jí)高*/ ops=pop(&st); /*將棧頂元素取出存入數(shù)組中*/ chk+=ops.op; if (st.size>0) ops=top(&st); /*進(jìn)行判空操作，棧為空結(jié)束*/ else break; push(&st,op); /*此時(shí)棧頂優(yōu)先級(jí)低，入棧*/ c=stri

14、+; /*索引自加檢索下一個(gè)字符*/ while(st.size!=0) /*最后判斷棧如果不為空*/ ops=pop(&st); /*取出棧內(nèi)元素存入數(shù)組中*/ chk+=ops.op; chk='0' /*將0作為結(jié)尾存入數(shù)組*/double CalResult(char exp) /*后綴表達(dá)式的計(jì)算*/ char c; numstack numst; /*建立數(shù)值棧*/ double d1,d2,dr; int k=0; /*后綴表達(dá)式的索引*/ int i=0; /*將字符轉(zhuǎn)化為浮點(diǎn)數(shù)的索引*/ char *s; char trans100; /*存字符表示的

15、一段數(shù)字*/ init2 (&numst); /*實(shí)現(xiàn)數(shù)值棧*/ c=expk+; while (c!='0') /*開(kāi)始掃描后綴表達(dá)式*/ if(c='+'|c='-'|c='*'|c='/'|c='%') /*如果是操作符*/ switch(c) case '+' : /*如果是加法操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=d1+d2; /*相加后入棧*/ push2(&numst,dr); break;

16、case '-' : /*如果是減法操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=d1-d2; /*相減后入棧*/ push2(&numst,dr); break; case '*' : /*如果是乘法操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=d1*d2; /*相乘后入棧*/ push2(&numst,dr); break; case '/' : /*如果是除法操作*/ d2=pop2(&numst); d1=p

17、op2(&numst); dr=d1/d2; /*相除后入棧*/ push2(&numst,dr); break; case '%' : /*如果是取余操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=(double)(int)d1%(int)d2); /*類(lèi)型轉(zhuǎn)化并取余后入棧*/ push2(&numst,dr); break; if (c>='0'&&c<='9'|c='.') /*如果是字符表示的數(shù)字*/ while(c&g

18、t;='0'&&c<='9'|c='.') transi+=c; /*將字符存入數(shù)組進(jìn)行下一個(gè)的掃描*/ c=expk+; transi+='0' /*將表示數(shù)字的字符串結(jié)束*/ i=0; s=trans; /*將指針指向該數(shù)組*/ d1=atof(s); /*利用函數(shù)將字符串轉(zhuǎn)化為浮點(diǎn)數(shù)*/ push2(&numst,d1); c=expk+; return pop2(&numst); /*最后結(jié)果將在數(shù)值棧中，取出作為返回值*/double Directcalresult(char str

19、) /*表達(dá)式的直接計(jì)算出結(jié)果*/ stack ms; /*建立符號(hào)棧*/ numstack mns; /*建立數(shù)值棧*/ double calculate(double od1,double od2,OpNode op); int index=0; /*str的索引*/ int len=strlen(str); char c; char trans100; /*存放數(shù)值的一段字符*/ int i=0; /*trans的索引*/ char * s; double d; OpNode tempn; /*存放當(dāng)前掃描的操作符*/ OpNode templn; double oda,odb,odr;

20、 double result; /*作為返回值返回結(jié)果*/ init (&ms); /*實(shí)現(xiàn)兩個(gè)棧*/ init2(&mns); while(index<len) /*開(kāi)始對(duì)用戶(hù)輸入的表達(dá)式進(jìn)行掃描*/ c=strindex+; if(c>='0'&&c<='9'|c='.') /*如果是數(shù)字字符或小數(shù)點(diǎn)*/ while(c>='0'&&c<='9'|c='.') transi+=c; /*將其存入數(shù)組掃描下一個(gè)*/ c=

21、strindex+; transi+='0' /*掃描完一個(gè)數(shù)結(jié)束數(shù)組*/ i=0; /*索引歸0*/ s=trans; d=atof(s); push2(&mns,d); /*轉(zhuǎn)化為浮點(diǎn)數(shù)入棧*/ if(c='+'|c='-') /*如果是+-*/ tempn.level=1; /*優(yōu)先級(jí)設(shè)為1*/ tempn.op=c; if(ms.size=0) push(&ms,tempn); /*棧為空直接入棧*/ else templn=top(&ms); while (templn.level>=tempn.level

22、) /*棧頂優(yōu)先級(jí)高*/ templn=pop(&ms); /*取出操作數(shù)和操作符計(jì)算*/ odb=pop2(&mns); oda=pop2(&mns); odr=calculate(oda,odb,templn); push2(&mns,odr); /*結(jié)算結(jié)果入棧*/ if(ms.size>0) templn=top(&ms); /*如果?？战Y(jié)束*/ else break; push(&ms,tempn); /*操作符入棧*/ if(c='*'|c='/'|c='%') /*如果是%操作*

23、/ tempn.level=2; /*定義優(yōu)先級(jí)為2*/ tempn.op=c; if(ms.size=0) push(&ms,tempn); /*?？罩苯尤霔?/ else templn=top(&ms); while (templn.level>=tempn.level) /*棧頂優(yōu)先級(jí)高*/ templn=pop(&ms); /*取出操作數(shù)和操作符計(jì)算*/ odb=pop2(&mns); oda=pop2(&mns); odr=calculate(oda,odb,templn); push2(&mns,odr); /*結(jié)算結(jié)果入棧*/

24、 if(ms.size>0) templn=top(&ms); else break; /*如果?？战Y(jié)束*/ templn=top(&ms); push(&ms,tempn); /*操作符入棧*/ if(c='(') /*如果是左括號(hào)*/ tempn.level=-1; tempn.op=c; /*直接入棧優(yōu)先級(jí)定位-1*/ push(&ms,tempn); if(c=')') /*如果是右括號(hào)*/ while(tempn.op!='(') /*遇到左括號(hào)結(jié)束*/ templn=pop(&ms); o

25、db=pop2(&mns); /*從數(shù)棧中取兩個(gè)數(shù)，從符號(hào)棧里取操作符*/ oda=pop2(&mns); odr=calculate(oda,odb,templn); /*計(jì)算出結(jié)果入棧*/ push2(&mns,odr); if (ms.size>0) tempn=top(&ms); else break; /*如果?？战Y(jié)束*/ pop(&ms); /*取出左括號(hào)*/ tempn=top(&ms); while(1) templn=pop(&ms); odb=pop2(&mns); /*從數(shù)棧中取兩個(gè)數(shù)，從符號(hào)棧里取操作

26、符*/ oda=pop2(&mns); odr=calculate(oda,odb,templn); /*計(jì)算出結(jié)果入棧*/ push2(&mns,odr); if (ms.size>0) tempn=top(&ms); /*如果?？战Y(jié)束*/ else break; result =pop2(&mns); /*最后的結(jié)果在數(shù)值棧中返回*/ return result;double calculate(double od1,double od2,OpNode op) /*已知操作符和操作數(shù)的計(jì)算*/ switch(op.op) case '+'

27、; : return od1+od2; case '-' : return od1-od2; /*判斷操作符是哪個(gè)執(zhí)行相應(yīng)計(jì)算*/ case '*' : return od1*od2; case '/' : return od1/od2; case '%' : return (double)(int)od1%(int)od2); return 0; /*如果上面的都沒(méi)有執(zhí)行返回0*/int check(char str,char chestr100) /*容錯(cuò)函數(shù)*/ char c; char cdivide; int i=0;

28、/*str的索引*/ stack che; /*括號(hào)匹配用到的棧*/ OpNode temp; int k=0; /*chestr的索引*/ int isinteger(char integer100); /*%計(jì)算是判斷是否是整數(shù)*/ char s110; /*%操作時(shí)存儲(chǔ)%左右的數(shù)字*/ char s210; int indexs1=0; /*s1s2的索引*/ int indexs2=0; int j; /*數(shù)組chestr索引*/ int flag=0; /*0-沒(méi)有出錯(cuò)1-有錯(cuò)*/ int tag=0; init (&che); c=stri; /*開(kāi)始掃描*/ for(j=

29、0;j<99;j+) chestrj=' ' /*數(shù)組初始化待以后加入''*/ chestrj='0' while(c!='0') if(c='(') /*如果是左括號(hào)就入棧*/ temp.op=c; push(&che,temp); if(c=')') /*如果是右括號(hào)*/ if(che.size>0) pop(&che); /*棧不為空就取出一個(gè)左括號(hào)*/ else flag=1; printf("缺少左括號(hào)n"); /*否則提示有錯(cuò)*/ ches

30、tri='' /*右括號(hào)下加''*/ if(c='/') /*判斷除數(shù)是否為0*/ j=0; cdivide=stri+1+j; /*取出除號(hào)后的數(shù)*/ while(cdivide>='0'&&cdivide<='9'|cdivide='.') /*如果是數(shù)或小數(shù)點(diǎn)就一直存*/ s1j+=cdivide; if(cdivide!='0'&&cdivide!='.') /*如果不是0則正確并結(jié)束*/ tag=1; break; cdivide=stri+j+1; if(!tag) /*如果tag為0則存在錯(cuò)誤除數(shù)為0*/ chestri+1='' flag=1; /*flag為1表示有錯(cuò)*/ if(c='%') /*取余操作的容錯(cuò)*/ while(stri-indexs1-1>='0'&am