將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式并計(jì)算

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告實(shí)驗(yàn)題目：使用鍵盤輸入表達(dá)式，計(jì)算表達(dá)式的值并輸出；將表達(dá)式轉(zhuǎn)化成后 綴表達(dá)式輸出，利用后綴表達(dá)式求表達(dá)式的值并輸出。實(shí)驗(yàn)?zāi)康模菏褂脳５牟僮骶帉戧P(guān)于數(shù)據(jù)結(jié)構(gòu)的程序。實(shí)驗(yàn)內(nèi)容：寫出程序并上機(jī)調(diào)試、通過。一、需求分析1、演示程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“請輸入表達(dá)式”時輸入中綴表達(dá)式。然后計(jì)算機(jī)終端輸出轉(zhuǎn)換后的后綴表達(dá)式及計(jì)算后的結(jié)果。2、程序執(zhí)行的命令包括：（1）構(gòu)造鏈棧；（2）輸入數(shù)據(jù)；（3）判斷輸入的表達(dá)式是否為非法表達(dá)式；（4）將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式；（5）計(jì)算表達(dá)式的值；（6）輸出。（7） 結(jié)束4、本程序能將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，并且

2、能計(jì)算表達(dá)式的值。5、輸入及輸出示例：例1 : 請輸入表達(dá)式6+3* (6+5 ) 后綴表達(dá)式：6 3 6 5 + * +計(jì)算結(jié)果為：39Press any key to con ti nue例2 :請輸入表達(dá)式6-3* (7+1ERROR表達(dá)式錯誤Press any key to con ti nue二概要設(shè)計(jì)1. 基本操作、struct node操作結(jié)果：創(chuàng)建結(jié)構(gòu)體(2) 、int Searchexpression(char string1)初始條件：表達(dá)式string1已經(jīng)存在。操作結(jié)果：判斷表達(dá)式是否非法(3) 、 struct node *lnitialization()操作結(jié)果：創(chuàng)

3、建棧鏈。(4) 、struct node *assort(struct node *s)string2 中。初始條件：string1、string2已存在。操作結(jié)果：將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式并存在(5) 、struct node *calcolate(struct node *s)操作結(jié)果：求出表達(dá)式的值2、模塊調(diào)用圖主程序模塊創(chuàng)建結(jié)構(gòu)體判斷表達(dá)式是否非法將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式表達(dá)式求值三詳細(xì)設(shè)計(jì)1、每個模塊：(1) 定義結(jié)構(gòu)體struct nodechar data;int num;struct node *n ext;；(2) 判斷表達(dá)式是否非法int Searchexpress

4、i on( char stri ng1)int i1,b1,b2;int m;m=strle n( stri ng1);if(stri ng10v0|stri ng109)printf(ERROR:表達(dá)式缺操作數(shù)！n);return(WRONG);for(i1=0;i1=m;i1+)if(stri ng1i1=()b1+;elseif(stri ng1i1=)b2+;if(b1!=b2)printf(ERROR:缺少括號 n);return(WRONG);for(i1=0;i1m;i1+)if(0=stri ng1i1&stri ng1i1v=9&0=stri ng1i1+1&strin g1

5、i1+1=9) printf(ERROR:表達(dá)式缺操作符！ n);return(WRONG);for(i1=0;i1=m;i1+)if(stri ng1i1=+&(stri ng1i1+1=+|stri ng1i1+1=-|stri ng1i1+1=*|stri ng1i1+1=/) printf(ERROR:表達(dá)式缺操作數(shù)！n);return(WRONG); elseif(stri ng1i1=-&(stri ng1i1+1=+|stri ng1i1+1=-|string1i1+1=*|stri ng1i1+1=/) printf(ERROR:表達(dá)式缺操作數(shù)！n);return(WRONG)

6、;elseif(stri ng1i1=*&(stri ng1i1+1=+|stri ng1i1+1=-|stri n g1i1+1=*|stri ng1i1+1=/)pri ntf(ERROR:表達(dá)式缺操作數(shù)！n);return(WRONG);elseif(stri ng1i1=/&(stri ng1i1+1=+|stri ng1i1+1=-|string1i1+1=*|stri ng1i1+1=/)pri ntf(ERROR: 表達(dá)式缺操作數(shù)！n);return(WRONG);return(RIGHT);(3) 、將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式struct node *assort(struc

7、t node *s)輸入字符串struct node *p,*top;int i;top=s;int m;char a;m=strle n( stri ng1);for(i=0;i=m;i+)a=stri ng1i;if(0data=a;p-n ext=top;top=p;break;case *:case /:stri ng2j= ;j+;if(top-data=*)|(top-data=/)string2j=top-data;j+; /比其高，現(xiàn)將棧頂運(yùn)算符出棧，再進(jìn)棧。top-data=a;break; else否,p=(struct node *)malloc(sizeof(struc

8、t no de);/直接進(jìn)棧p-data=a;p-n ext=top;top=p;break;case +:case -:stri ng2j= ;j+;if(top-data=+|top-data=-|top-data=*|top-data=/)stri ng2j=top-data;j+;top-data=a;break;elsep-data=a;p-n ext=top;top=p; break;case ):stri ng2j= ;j+;if(top-data=)pri ntf(i nput error);break;while(top-data!=() stri ng2j=top-data

9、;j+;p=top;top=top-n ext;free(p);p=top;top=top-n ext;free(p);break;while(top-data!=)stri ng2j=top-data;j+;p=top;top=top-n ext;free(p);stri ng2j=#;printf(后綴表達(dá)式為:);for(i=0;ij;i+)if(stri ng2i!=)prin tf(%c ,stri ng2i);prin tf(n );return top;(4)表達(dá)式求值struct node *calcolate(struct node *s)struct node *top,*

10、p;char *q;int x,y,a;int i,n;top=s;指向棧頂?shù)闹羔榝or(i=0;i=0&stri ng2iv=9)q=&stri ng2i;a=atoi(q);for(n=i;stri ng2 n=0&stri ng2 nv=9 ;n+)p=(struct node *)malloc(sizeof(struct node );p-num=a;p-n ext=top;top=p;i=n-1;elseif(string2i=#)/遇#號結(jié)束標(biāo)志，輸出棧中的最后計(jì)算結(jié)果printf(計(jì)算結(jié)果為:%dn,top-num);elseif(string2i=)else y=top-nu

11、m;p=top;top=top-n ext;free(p);x=top-nu m;p=top;top=top-n ext;free(p);switch(stri ng2i)case +:a=x+y;p=(struct node *)malloc(sizeof(struct no de);p-num=a;p-n ext=top;top=p;break;case -:a=x-y;p=(struct node *)malloc(sizeof(struct node );p-num=a;p-n ext=top;top=p;break;case *:a=x*y;p=(struct node *)mall

12、oc(sizeof(struct node );p-num=a;p-n ext=top;top=p;break;case 7:if(y=0)printf(ERROR:除數(shù)為零!n);a=(float)x/y;p-num=a;p-n ext=top;top=p;p=(struct node *)malloc(sizeof(struct node );break;return 0;(5)、主函數(shù)void mai n()struct node *top,*head;top=l ni tializatio n();建立一個鏈棧，并返回棧頂指針printf(請輸入表達(dá)式：n);gets(stri ng1

13、);if(Searchexpressio n(stri ng1)head=assort(top);/中綴轉(zhuǎn)化為后綴表達(dá)式calcolate(head);2、完整函數(shù) #i nclude#i nclude#i ncludevstri ng.h#i nclude#defi ne MAX 60#define RIGHT 1#defi ne WRONG 0#defi ne DEMAX 15#defi ne NULL 0char stri ng1MAX;char stri ng2MAX;int j=0;struct n ode / 定義結(jié)構(gòu)體。char data;int num;struct node

14、*n ext;/判斷非法表達(dá)式;int Searchexpressi on( char stri ng1)int i1,b1,b2;int m;m=strle n(stri ng1);if(stri ng10v0|stri ng109)printf(ERROR:表達(dá)式缺操作數(shù)！ n);return(WRONG);for(i1=0;i1=m;i1+)if(stri ng1i1=()b1+;elseif(stri ng1i1=)b2+;if(b1!=b2)printf(ERROR:缺少括號 n);return(WRONG);for(i 1= 0;i1m;i1+)if(0=stri ng1i1&st

15、ri ng1i1v=9& 0=stri ng1i1+1&stri ng1i1+1v=9) printf(ERROR:表達(dá)式缺操作符！ n);return(WRONG);for(i1=0;i1data=;top-num=0;top- next=NULL;return top;struct node *assort(struct node *s)/輸入字符串struct node *p,*top;int i;top=s;int m;char a;m=strle n(stri ng1);for(i=0;i=m;i+)a=stri ng1i;if(Ov=stri ng1i&stri ng1idata=

16、a;p-n ext=top;top=p;break;case /:strin g2j= ;j+;/比其咼，現(xiàn)將棧頂運(yùn)算符出if(top-data=*)|(top-data=/)stri ng2j=top-data;j+;棧，再進(jìn)棧top-data=a;break;else否，直接p=(struct node *)malloc(sizeof(struct no de);/進(jìn)棧p-data=a;p-n ext=top;top=p;break;case +:case -:stri ng2j= ;j+;if(top-data=+|top-data=-|top-data=*|top-data=7)str

17、i ng2j=top-data;j+;top-data=a;break;else p=(struct node *)malloc(sizeof(struct no de);p-data=a;p-n ext=top;top=p;break;case ):stri ng2j= ;j+;if(top-data=)pri ntf(i nput error);break;while(top-data!=()stri ng2j=top-data;j+;p=top;top=top-n ext;free(p); p=top;top=top-n ext;free(p);break;while(top-data!

18、=)stri ng2j=top-data;j+;p=top;top=top-n ext;free(p);strin g2j=#;printf(后綴表達(dá)式為:);for(i=0;ij;i+)if(stri ng2i!=)prin tf(%c ,stri ng2i);return top;prin tf(n );/計(jì)算表達(dá)式的值struct node *calcolate(struct node *s)struct node *top,*p;char *q;int x,y,a;int i,n;top=s;/指向棧頂?shù)闹羔榝or(i=0;i=0&stri ng2iv=9)q=&stri ng2i;a

19、=atoi(q);for(n=i;stri ng2 n=0&stri ng2 nnum=a;p-n ext=top;top=p;i=n-1;elseif(string2i=#)/遇#號結(jié)束標(biāo)志，輸出棧中的最后計(jì)算結(jié)果 elseprintf(計(jì)算結(jié)果為:%dn,top-num);if(stri ng2i= ) else y=top-nu m;p=top;top=top-n ext;free(p);x=top-nu m;p=top;top=top-n ext;free(p);switch(stri ng2i)case +:a=x+y;p=(struct node *)malloc(sizeof(struct no de);p-num=a;p-n ext=top;top=p;break;case -:a=x-y;p=(struct node *)malloc(sizeo