1、1表達式求值問題表達式是數據運算的基本形式。人們的書寫習慣是中綴式，如：11+22*(7-4)/3。中綴式的計算按運算符的優先級及括號優先的原則，相同級別從左到右進行計算。表達式還有后綴式如：2274-*3/11+和前綴式如：+11/*22-743。后綴表達式和前綴表達式中沒有括號，給計算帶來方便。如后綴式計算時按運算符出現的先后進行計算。本設計的主要任務是進行表達式形式的轉換及不同形式的表達式計算。2.數據結構設計1表達式求值問題定義存儲中綴表達式的結點類型由丁表達式中有字符與數字兩種類型，故定義結點一個標志域data,標志結點存儲的為字符data=2還是數字data=1,再尋找結點中對應的

2、存儲位置，讀取數字域data1字符域data2。而在前綴表達式時，存在表達式逆序，因表達式類型不統一，用棧逆序極不方便，選擇構建雙向鏈表，存儲表達式。typedefstructNode(intdata;intdata1;chardata2;structNode*next;Lnode;typedefstructNode2/定義存儲前綴表達式的結點類型(intdata;intdata1;chardata2;structNode2*next;structNode2*prior;Lnode2;3.運行、測試與分析1表達式求值問題1按提示輸入中綴表達式，如圖。如輸入中綴表達式不正確，提示輸入有誤，如圖1

3、.2,1.3所示。圖a圖(2)選擇表達式轉換并求值方式。按“1”選擇中綴表達式求值，如圖1.4所示。3按“2”選擇中綴表達式轉變為后綴表達式并求值，如圖1.5所示圖1.5(4)按“3”選擇中綴表達式轉變為前綴表達式并求值，如圖1.6所示'C:'Users.Adninistr占t&rDes<topDebugJntitledLexe'疳鋸裊遷策值，輸入2后蝴表達式求值/-*34FR3411=1R2Pprs?nukeuto輸入3前綴表達式求值3nnritimiiR圖1.6附錄：源代碼1表達式求值問題#include<stdio.h>#include&

4、lt;stdlib.h>#defineMAXNUM100typedefstructNode/定義存儲中綴表達式的結點類型intdata;intdata1;chardata2;structNode*next;Lnode;typedefstructNode2定義存儲前綴表達式的結點類型intdata;intdata1;chardata2;structNode2*next;structNode2*prior;Lnode2;typedefintselemtype1;定義運算數棧的結點typedefstruct定義運算數棧的類型selemtype1*base;selemtype1*top;sqst

5、ack1;voidInitStack1(sqstack1&s)新建一個空運算數棧s.base=(selemtype1*)malloc(MAXNUM*sizeof(selemtype1);s.top=s.base;if(!s.base)printf("出錯：申請空間失敗！n");voidPush1(sqstack1&s,selemtype1&e)運算數棧，入棧：插入元素e為新的棧頂元素if(s.top-s.base>=MAXNUM)printf("出錯：表達式過長！1n");*s.top+=e;voidGetTop1(sqst

6、ack1s,selemtype1&e)運算數棧，用e返回棧頂元素e=*(s.top-1);voidPopopnd1(sqstack1&s,selemtype1&e)運算數棧，退棧：刪除棧頂元素，并用e返回其威e=*-s.top;intstackempy1(sqstack1s)運算數棧，假設為空棧返回1,否則返回0if(s.top=s.base)return1;elsereturn0;typedefcharselemtype2;定義運算符棧的結點類型typedefstruct定義運算符棧類型selemtype2*base;selemtype2*top;sqstack2;v

7、oidInitStack2(sqstack2&s)新建一個空運算符棧(s.base=(selemtype2*)malloc(MAXNUM*sizeof(selemtype2);s.top=s.base;if(!s.base)printf("出錯：申請空間失敗！n");voidPush2(sqstack2&s,selemtype2&e)運算符棧，入棧：插入元素e為新的棧頂元素(if(s.top-s.base>=MAXNUM)printf(”出錯：表達式過長！2n");*s.top+=e;voidGetTop2(sqstack2s,sel

8、emtype2&e)運算符棧，用e返回棧頂元素(e=*(s.top-1);voidPopopnd2(sqstack2&s,selemtype2&e)運算符棧，退棧：刪除棧頂元素，并用e返回其柿(e=*-s.top;intstackempy2(sqstack2s)運算符棧，假設為空棧返回1,否則返回0if(s.top=s.base)return1;elsereturn0;voidpriority(charc,int&i)確定運算符優先級(if(c='*'|c='/'|c='%')i=2;elseif(c='+

9、'|c='-')i=1;elsei=0;intcompare(chara,charb)/比較棧頂元素運算符與外部運算符優先級大小，外部優先級大則返回1,反之返回0(intin,out;priority(a,in);priority(b,out);if(out>in)return1;elsereturn0;voidOperat(sqstack1&OPND,sqstack2&OPTR)(intnum1,num2,num;charc;Popopnd1(OPND,num2);Popopnd1(OPND,num1);Popopnd2(OPTR,c);swit

10、ch(c)(case'+':num=num1+num2;break;case'-':num=num1-num2;break;case'*':num=num1*num2;break;case'/':num=num1/num2;break;case'%':num=num1%num2;break;Push1(OPND,num);voidOperatqianzhui(sqstack1&OPND,sqstack2&OPTR)(intnum1,num2,num;charc;Popopnd1(OPND,num1)

11、;Popopnd1(OPND,num2);Popopnd2(OPTR,c);switch(c)(case'+':num=num1+num2;break;case'-':num=num1-num2;break;case'*':num=num1*num2;break;case'/':num=num1/num2;break;case'%':num=num1%num2;break;Push1(OPND,num);后綴表達式求值voidhouzhuiqiuzhi(Lnode*p,int&e)(sqstack1OPND

12、;運算數棧sqstack2OPTR;運算符棧intn;charc;p=p->next;InitStack1(OPND);InitStack2(OPTR);while(p)(switch(p->data)(case1:n=p->data1;Push1(OPND,n);break;case2:c=p->data2;Push2(OPTR,c);Operat(OPND,OPTR);break;default:printf("結點有誤");break;p=p->next;Popopnd1(OPND,n);e=n;中綴表達式求值voidzhongzhui(

13、Lnode*p)sqstack1OPND;運算數棧sqstack2OPTR;運算符棧intn;charc,c2;Lnode*first;first=p;p=p->next;InitStack1(OPND);InitStack2(OPTR);while(!stackempy2(OPTR)|p)while(p)switch(p->data)case1:n=p->data1;Push1(OPND,n);break;case2:c=p->data2;if(stackempy2(OPTR)Push2(OPTR,c);elseswitch(c)case'(':Pus

14、h2(OPTR,c);break;case')':GetTop2(OPTR,c2);while(c2!='(')Operat(OPND,OPTR);GetTop2(OPTR,c2);Popopnd2(OPTR,c2);break;default:GetTop2(OPTR,c2);if(compare(c2,c)Push2(OPTR,c);elseOperat(OPND,OPTR);Push2(OPTR,c);break;break;default:printf("結點有誤");break;p=p->next;while(!stackem

15、py2(OPTR)Operat(OPND,OPTR);Popopnd1(OPND,n);p=first->next;while(p)(if(p->data=1)printf("%d",p->data1);if(p->data=2)printf("%c",p->data2);p=p->next;printf("=%d",n);中綴表達式轉化為后voidhouzhui(Lnode*p)綴表達式sqstack2OPTR;運算符棧Lnode*r,*q,*head;intn;charc,c2;InitStac

16、k2(OPTR);p=p->next;q=(Lnode*)malloc(sizeof(structNode);head=q;while(p)switch(p->data)case1:n=p->data1;r=(Lnode*)malloc(sizeof(structNode);q->next=r;q=q->next;q->data=1;q->data1=n;break;if(stackempy2(OPTR)Push2(OPTR,c);elseswitch(c)case'(':Push2(OPTR,c);break;case')&#

17、39;:Popopnd2(OPTR,c2);while(c2!='(')r=(Lnode*)malloc(sizeof(structNode);q->next=r;q=q->next;q->data=2;q->data2=c2;Popopnd2(OPTR,c2);break;default:GetTop2(OPTR,c2);while(!compare(c2,c)Popopnd2(OPTR,c2);r=(Lnode*)malloc(sizeof(structNode);q->next=r;q=q->next;q->data=2;q-&g

18、t;data2=c2;GetTop2(OPTR,c2);Push2(OPTR,c);break;break;default:printf("結點有誤");break;p=p->next;while(!stackempy2(OPTR)(Popopnd2(OPTR,c2);r=(Lnode*)malloc(sizeof(structNode);q->next=r;q=q->next;q->data=2;q->data2=c2;q->next=NULL;q=head->next;while(q)if(q->data=1)printf

19、("%d",q->data1);if(q->data=2)printf("%c”,q->data2);q=q->next;houzhuiqiuzhi(head,n);printf("=%d",n);voidqianzhuiqiuzhi(Lnode2*p,int&e)前綴表達式求值sqstack1OPND;運算數棧sqstack2OPTR;運算符棧intn;charc;Lnode2*head;head=p;p=p->next;InitStackl(OPND);InitStack2(OPTR);while(p!

20、=head)switch(p->data)case1:n=p->data1;Push1(OPND,n);break;case2:c=p->data2;Push2(OPTR,c);Operatqianzhui(OPND,OPTR);break;default:printf("結點有誤");break;p=p->next;Popopnd1(OPND,n);e=n;voidqianzhui(Lnode*p)式(sqstack2OPTR;運算符棧InitStack2(OPTR);intn;charc,c2;Lnode*first;Lnode2*q,*head

21、,*r,*head2,*s;first=p;p=p->next;q=(Lnode2*)malloc(sizeof(structNode2);環鏈表head=q;while(p)r=(Lnode2*)malloc(sizeof(structNode2);q->next=r;r->prior=q;q=q->next;q->data=p->data;q->data1=p->data1;q->data2=p->data2;p=p->next;q->next=head;head->prior=q;s=(Lnode2*)mall

22、oc(sizeof(structNode2);鏈表head2=s;中綴表達式轉化為前綴表達/建立存中綴表達式的雙向循/建立存前綴表達式的雙向循環while(q!=head)(switch(q->data)(case1:n=q->data1;r=(Lnode2*)malloc(sizeof(structNode2);s->next=r;r->prior=s;s=s->next;s->data=1;s->data1=n;break;case2:c=q->data2;if(stackempy2(OPTR)Push2(OPTR,c);else(GetTo

23、p2(OPTR,c2);if(c2=')')Push2(OPTR,c);else(switch(c)(case')':Push2(OPTR,c);break;case'(':Popopnd2(OPTR,c2);while(c2!=')')(r=(Lnode2*)malloc(sizeof(structNode2);s->next=r;r->prior=s;s=s->next;s->data=2;s->data2=c2;Popopnd2(OPTR,c2);break;default:GetTop2(OP

24、TR,c2);while(!compare(c2,c)(Popopnd2(OPTR,c2);r=(Lnode2*)malloc(sizeof(structNode2);s->next=r;r->prior=s;s=s->next;s->data=2;s->data2=c2;GetTop2(OPTR,c2);Push2(OPTR,c);break;break;default:printf("結點有誤");break;q=q->prior;while(!stackempy2(OPTR)Popopnd2(OPTR,c2);r=(Lnode2*)

25、malloc(sizeof(structNode2);s->next=r;r->prior=s;s=s->next;s->data=2;s->data2=c2;s->next=head2;head2->prior=s;while(s!=head2)(if(s->data=1)printf("%d”,s->data1);if(s->data=2)printf("%c”,s->data2);s=s->prior;qianzhuiqiuzhi(head2,n);printf("=%d",n

26、);intmain()(charn10;charc;inti,j,k,a,b,z,y,e;Lnode*p,*q,*first;i=0;e=1;a=0;b=1;z=0;y=0;p=(Lnode*)malloc(sizeof(structNode);first=p;printf("請輸入中綴表達式");do(c=getchar();if('0'<=c&&c<='9')(ni=c;i+；else(switch(c)(case'+':case'-':case'*':case'/':case'%':case'(':case')':case'n':(if(n0>'0'&&