【C語言《數(shù)據(jù)結(jié)構(gòu)》實驗報告】表達式的轉(zhuǎn)換.doc

數(shù)據(jù)結(jié)構(gòu)實驗報告實驗題目: 使用鍵盤輸入表達式，計算表達式的值并輸出；將表達式轉(zhuǎn)化成后綴表達式輸出，利用后綴表達式求表達式的值并輸出。實驗目的：使用棧的操作編寫關于數(shù)據(jù)結(jié)構(gòu)的程序。實驗內(nèi)容：寫出程序并上機調(diào)試、通過。一、需求分析1、演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“請輸入表達式”時輸入中綴表達式。然后計算機終端輸出轉(zhuǎn)換后的后綴表達式及計算后的結(jié)果。2、程序執(zhí)行的命令包括：（1）構(gòu)造鏈棧；（2）輸入數(shù)據(jù)；（3）判斷輸入的表達式是否為非法表達式；（4）將中綴表達式轉(zhuǎn)換為后綴表達式；（5）計算表達式的值；（6）輸出。（7）結(jié)束4、本程序能將中綴表達式轉(zhuǎn)換為后綴表達式，并且能計算表達式的值。5、輸入及輸出示例：例1：請輸入表達式6+3*（6+5）后綴表達式：6 3 6 5 + * +計算結(jié)果為：39press any key to continue 例2：請輸入表達式6-3*（7+1error:表達式錯誤press any key to continue 二 概要設計1基本操作(1)、struct node操作結(jié)果：創(chuàng)建結(jié)構(gòu)體(2)、int searchexpression(char string1)初始條件：表達式string1已經(jīng)存在。操作結(jié)果：判斷表達式是否非法(3)、struct node *initialization()操作結(jié)果：創(chuàng)建棧鏈。(4)、struct node *assort(struct node *s)初始條件：string1、string2已存在。操作結(jié)果：將中綴表達式轉(zhuǎn)換為后綴表達式并存在string2中。(5)、struct node *calcolate(struct node *s)操作結(jié)果：求出表達式的值2、模塊調(diào)用圖主程序模塊創(chuàng)建結(jié)構(gòu)體判斷表達式是否非法將中綴表達式轉(zhuǎn)換為后綴表達式表達式求值三 詳細設計1、每個模塊：(1) 定義結(jié)構(gòu)體struct node char data;int num;struct node *next; (2) 判斷表達式是否非法int searchexpression(char string1) int i1,b1,b2;int m;m=strlen(string1);if(string109)printf(error:表達式缺操作數(shù)！n);return(wrong);for(i1=0;i1=m;i1+)if(string1i1=()b1+;elseif(string1i1=)b2+;if(b1!=b2)printf(error:缺少括號n);return(wrong);for(i1=0;i1m;i1+)if(0=string1i1&string1i1=9&0=string1i1+1&string1i1+1=9) printf(error:表達式缺操作符！n);return(wrong);for(i1=0;i1=m;i1+)if(string1i1=+&(string1i1+1=+|string1i1+1=-|string1i1+1=*|string1i1+1=/) printf(error:表達式缺操作數(shù)！n);return(wrong);elseif(string1i1=-&(string1i1+1=+|string1i1+1=-|string1i1+1=*|string1i1+1=/) printf(error:表達式缺操作數(shù)！n);return(wrong);elseif(string1i1=*&(string1i1+1=+|string1i1+1=-|string1i1+1=*|string1i1+1=/)printf(error:表達式缺操作數(shù)！n);return(wrong);elseif(string1i1=/&(string1i1+1=+|string1i1+1=-|string1i1+1=*|string1i1+1=/)printf(error:表達式缺操作數(shù)！n);return(wrong);return(right); (3)、將中綴表達式轉(zhuǎn)換為后綴表達式struct node *assort(struct node *s)/輸入字符串struct node *p,*top;int i;top=s;int m;char a;m=strlen(string1); for(i=0;i=m;i+)a=string1i;if(0=string1i&string1idata=a;p-next=top;top=p;break; case *:case /:string2j= ;j+;if(top-data=*)|(top-data=/)string2j=top-data;j+; /比其高，現(xiàn)將棧頂運算符出棧，再進棧。top-data=a;break;elsep=(struct node *)malloc(sizeof(struct node);/否，直接進棧p-data=a;p-next=top;top=p;break;case +:case -:string2j= ;j+;if(top-data=+|top-data=-|top-data=*|top-data=/)string2j=top-data;j+;top-data=a;break;else p=(struct node *)malloc(sizeof(struct node);p-data=a;p-next=top;top=p;break; case ):string2j= ;j+;if(top-data=)printf(input error);break;while(top-data!=()string2j=top-data;j+;p=top;top=top-next;free(p);p=top;top=top-next;free(p);break;while(top-data!=)string2j=top-data;j+;p=top;top=top-next;free(p);string2j=#;printf(后綴表達式為:);for(i=0;ij;i+)if(string2i!= )printf(%c ,string2i);printf(n );return top; (4)表達式求值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&string2i=0&string2nnum=a;p-next=top;top=p;i=n-1;elseif(string2i=#) /遇#號結(jié)束標志，輸出棧中的最后計算結(jié)果printf(計算結(jié)果為:%dn,top-num);elseif(string2i= )elsey=top-num;p=top;top=top-next;free(p);x=top-num;p=top;top=top-next;free(p);switch(string2i)case +:a=x+y;p=(struct node *)malloc(sizeof(struct node);p-num=a;p-next=top;top=p;break;case -:a=x-y;p=(struct node *)malloc(sizeof(struct node );p-num=a;p-next=top;top=p;break;case *:a=x*y;p=(struct node *)malloc(sizeof(struct node );p-num=a;p-next=top;top=p;break;case /:if(y=0) printf(error:除數(shù)為零!n);a=(float)x/y;p=(struct node *)malloc(sizeof(struct node );p-num=a;p-next=top;top=p;break;return 0;(5)、主函數(shù)void main()struct node *top,*head;top=initialization();/建立一個鏈棧，并返回棧頂指針printf(請輸入表達式：n);gets(string1);if(searchexpression(string1)head=assort(top);/中綴轉(zhuǎn)化為后綴表達式calcolate(head);2、完整函數(shù)#include#include#include#include#define max 60#define right 1#define wrong 0#define demax 15#define null 0char string1max;char string2max;int j=0;struct node /定義結(jié)構(gòu)體。char data;int num;struct node *next;int searchexpression(char string1) /判斷非法表達式int i1,b1,b2;int m;m=strlen(string1);if(string109)printf(error:表達式缺操作數(shù)！n);return(wrong);for(i1=0;i1=m;i1+)if(string1i1=()b1+;elseif(string1i1=)b2+;if(b1!=b2)printf(error:缺少括號n);return(wrong);for(i1=0;i1m;i1+)if(0=string1i1&string1i1=9&0=string1i1+1&string1i1+1=9) printf(error:表達式缺操作符！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=strlen(string1); for(i=0;i=m;i+)a=string1i;if(0=string1i&string1idata=a;p-next=top;top=p;break; case *:case /:string2j= ;j+;if(top-data=*)|(top-data=/)string2j=top-data;j+; /比其高，現(xiàn)將棧頂運算符出棧，再進棧。top-data=a;break;elsep=(struct node *)malloc(sizeof(struct node);/否，直接進棧p-data=a;p-next=top;top=p;break;case +:case -:string2j= ;j+;if(top-data=+|top-data=-|top-data=*|top-data=/)string2j=top-data;j+;top-data=a;break;else p=(struct node *)malloc(sizeof(struct node);p-data=a;p-next=top;top=p;break; case ):string2j= ;j+;if(top-data=)printf(input error);break;while(top-data!=()string2j=top-data;j+;p=top;top=top-next;free(p);p=top;top=top-next;free(p);break;while(top-data!=)string2j=top-data;j+;p=top;top=top-next;free(p);string2j=#;printf(后綴表達式為:);for(i=0;ij;i+)if(string2i!= )printf(%c ,string2i);printf(n );return top;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&string2i=0&string2nnum=a;p-next=top;top=p;i=n-1;elseif(string2i=#) /遇#號結(jié)束標志，輸出棧中的最后計算結(jié)果printf(計算結(jié)果為:%dn,top-num);elseif(string2i= )elsey=top-num;p=top;top=top-next;free(p);x=top-num;p=top;top=top-next;free(p);switch(string2i)case +:a=x+y;p=(struct node *)malloc(sizeof(struct node);p-num=a;p-next=top;top=p;break;case -:a=x-y;p=(struct node *)malloc(sizeof(struct node );p-num=a;p-next=top;top=p;break;case *:a=x*y;p=(struct node *)malloc(sizeof(struct node );p-num=a;p-next=top;top=p;break;case /:if(y=0) printf(error:除數(shù)為零!n);a=(float)x/y;p=(struct node *)malloc(sizeof(struct node );p-num=a;p-next=top;top=p;break;return 0;void main()/主函數(shù)struct node *top,*head;top=initialization();/建立一個鏈棧，并返回棧頂指針printf(請輸入表達式：n);gets(string1);if(searchexpression(string1)head=assort(top);/中綴轉(zhuǎn)化為后綴表達式calcolate(head);四 使用說明、測試分析及結(jié)果1、運行界面：microsoft visual c/c+2、測試結(jié)果例1：請輸入表達式6+3*（6+5）后綴表達式：6 3 6 5 + * +計算結(jié)果為：39press any key to continue 例2：請輸入表達式6-3*（7+1error:表達式錯誤press any key to continue 五、實驗總結(jié)教師評語：實驗成績：指導教師簽名： 批閱日期： ut2apodfxxc02gybkskcww97mrqqwhoj5tl15zt6jipyytycummtarp3v1n5luizi3xh3bhwyreko8d9g7nmzqowpjetldrw08gvs8dsdqqygc3ce7moo2tlf0jf1gk74iuxybmtivr97ckrfvqult5fn2t6mpjr6rbzvpsortzvij5nb5ndvvsr4iwr1twlfkglspzuhrjq3cmzu98euouijdlszqpmvrw9zkupxf8wfug9l2g9277g2rtipa1ypczeuqxpkbhtvdcooqozxuz3vjrzmocijym62zchmeootyes8ebmm932tbz2yo09rtszeys8zrd2yktj8l6jeazvajnfbtrylvsm6ofbftoxvrffn7owiygjlamkunxjybz5rrb7r4vsur9zpfzfmfsjhcfca37lnw2vvlrkn7r8psz1bn6oric5hu5z6hcxayqynpog8duybawqsl20csg06dh2sm8hltgpkicskrgopdpuhbj1lmpk7lydvc6nnmwl3fwhzftfvyaary7lhssxj10v3ph3y19bxyr77ib7cpzsu2tijqe3hkqkkau9kskcphkxuikvvyjzpg2yijrkqfbggovyqkuxnwi9omnjtt6qilzxtyrf7d20fbmabcfiixrqkusvnxbppfuxyq1fjskfsubkgs2duvqc9sz4jkbgn4qqv66pyoarjurnfj3txyfclzieeptwfjthpheipdfnqnr2hjqkv2dzwtmpdjqkbcxmovdsjqctjagjmdlskpgad2s0h0vmzgaht36gyuez7umank1ndreubeqdgrx0venqgnsyib2ilq3siqrnl4m56t7z8y8da5k0kupn5nzg4jvjdtffhyt82aogqkxo4vblmleiy2p7hthbho07rcfttxodydppdtqso7wxd0j6fkklgm4wodzplhtrr2xgqn13hqy59zu1gegdyqnihntavsieuefqcyfucjwd3vk5i7ykmhundmiz ut2apodfxxc02gybkskcww97mrqqwhoj5tl15zt6jipyytycummtarp3v1n5luizi3xh3bhwyreko8d9g7nmzqowpjetldrw08gvs8dsdqqygc3ce7moo2tlf0jf1gk74iuxybmtivr97ckrfvqult5fn2t6mpjr6rbzvpsortzvij5nb5ndvvsr4