實驗五 中綴表達式轉(zhuǎn)化為后綴表達式算法(昆工版本)

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

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

3、p; int size; /*表示棧內(nèi)元素的個數(shù)*/ stack; /*定義符號棧*/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); /*聲明要用到的各個函數(shù)*/ double

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

7、tf("%sn",str); printf(chestr); /*根據(jù)輸入情況指出錯誤的地方*/ 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("后綴表達式為:%sn",exp); printf("運算結(jié)果為： %fn",CalResult(exp); /*調(diào)用函數(shù)計算后綴表達式*/ printf("Try agian<y/n>:"); while(ch=getchar(),ch!='n'&&ch!='y'); system("pause"); while(ch!='n');void change (char

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

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

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

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

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

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

15、一段數(shù)字*/ init2 (&numst); /*實現(xiàn)數(shù)值棧*/ c=expk+; while (c!='0') /*開始掃描后綴表達式*/ 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); /*類型轉(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ù)組進行下一個的掃描*/ c=expk+; transi+='0' /*將表示數(shù)字的字符串結(jié)束*/ i=0; s=trans; /*將指針指向該數(shù)組*/ d1=atof(s); /*利用函數(shù)將字符串轉(zhuǎn)化為浮點數(shù)*/ push2(&numst,d1); c=expk+; return pop2(&numst); /*最后結(jié)果將在數(shù)值棧中，取出作為返回值*/double Directcalresult(char str

19、) /*表達式的直接計算出結(jié)果*/ stack ms; /*建立符號棧*/ 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; /*存放當前掃描的操作符*/ OpNode templn; double oda,odb,odr;

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

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

22、) /*棧頂優(yōu)先級高*/ templn=pop(&ms); /*取出操作數(shù)和操作符計算*/ 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)先級為2*/ tempn.op=c; if(ms.size=0) push(&ms,tempn); /*?？罩苯尤霔?/ else templn=top(&ms); while (templn.level>=tempn.level) /*棧頂優(yōu)先級高*/ templn=pop(&ms); /*取出操作數(shù)和操作符計算*/ 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='(') /*如果是左括號*/ tempn.level=-1; tempn.op=c; /*直接入棧優(yōu)先級定位-1*/ push(&ms,tempn); if(c=')') /*如果是右括號*/ while(tempn.op!='(') /*遇到左括號結(jié)束*/ templn=pop(&ms); o

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

26、符*/ oda=pop2(&mns); odr=calculate(oda,odb,templn); /*計算出結(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ù)的計算*/ switch(op.op) case '+'

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

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

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

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