C語言實(shí)現(xiàn)中綴、后綴、前綴表達(dá)式 相互轉(zhuǎn)化并求值_第1頁
C語言實(shí)現(xiàn)中綴、后綴、前綴表達(dá)式 相互轉(zhuǎn)化并求值_第2頁
C語言實(shí)現(xiàn)中綴、后綴、前綴表達(dá)式 相互轉(zhuǎn)化并求值_第3頁
C語言實(shí)現(xiàn)中綴、后綴、前綴表達(dá)式 相互轉(zhuǎn)化并求值_第4頁
C語言實(shí)現(xiàn)中綴、后綴、前綴表達(dá)式 相互轉(zhuǎn)化并求值_第5頁
已閱讀5頁,還剩15頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、1.問題描述(1)表達(dá)式求值問題 表達(dá)式是數(shù)據(jù)運(yùn)算的基本形式。人們的書寫習(xí)慣是中綴式,如:11+22*(7-4)/3。中綴式的計(jì)算按運(yùn)算符的優(yōu)先級(jí)及括號(hào)優(yōu)先的原則,相同級(jí)別從左到右進(jìn)行計(jì)算。表達(dá)式還有后綴式(如:22 7 4 - * 3 / 11 +)和前綴式(如:+ 11 / * 22 7 4 3)。后綴表達(dá)式和前綴表達(dá)式中沒有括號(hào),給計(jì)算帶來方便。如后綴式計(jì)算時(shí)按運(yùn)算符出現(xiàn)的先后進(jìn)行計(jì)算。本設(shè)計(jì)的主要任務(wù)是進(jìn)行表達(dá)式形式的轉(zhuǎn)換及不同形式的表達(dá)式計(jì)算。2. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)(1)表達(dá)式求值問題 由于表達(dá)式中有字符與數(shù)字兩種類型,故定義結(jié)點(diǎn)一個(gè)標(biāo)志域data,標(biāo)志結(jié)點(diǎn)存儲(chǔ)的為字符data=2還是數(shù)

2、字data=1,再尋找結(jié)點(diǎn)中對(duì)應(yīng)的存儲(chǔ)位置,讀取數(shù)字域data1,字符域data2。而在前綴表達(dá)式時(shí),存在表達(dá)式逆序,因表達(dá)式類型不統(tǒng)一,用棧逆序極不方便,選擇構(gòu)建雙向鏈表,存儲(chǔ)表達(dá)式。typedef struct Node /定義存儲(chǔ)中綴表達(dá)式的結(jié)點(diǎn)類型int data; int data1; char data2; struct Node *next;Lnode; typedef struct Node2 /定義存儲(chǔ)前綴表達(dá)式的結(jié)點(diǎn)類型int data; int data1; char data2; struct Node2 *next; struct Node2 *prior;Lnode

3、2; 3. 運(yùn)行、測(cè)試與分析(1)表達(dá)式求值問題(1)按提示輸入中綴表達(dá)式,如圖1.1所示。如輸入中綴表達(dá)式不正確,提示輸入有誤,如圖1.2,1.3所示。圖1.1圖1.2圖1.3(2) 選擇表達(dá)式轉(zhuǎn)換并求值方式。按“1”選擇中綴表達(dá)式求值,如圖1.4所示。圖1.4(3)按“2”選擇中綴表達(dá)式轉(zhuǎn)變?yōu)楹缶Y表達(dá)式并求值,如圖1.5所示。圖1.5(4) 按“3”選擇中綴表達(dá)式轉(zhuǎn)變?yōu)榍熬Y表達(dá)式并求值,如圖1.6所示。圖1.6附錄:源代碼(1)表達(dá)式求值問題#include<stdio.h> #include<stdlib.h>#define MAXNUM 100typedef s

4、truct Node /定義存儲(chǔ)中綴表達(dá)式的結(jié)點(diǎn)類型int data; int data1; char data2; struct Node *next;Lnode; typedef struct Node2 /定義存儲(chǔ)前綴表達(dá)式的結(jié)點(diǎn)類型int data; int data1; char data2; struct Node2 *next; struct Node2 *prior;Lnode2; typedef int selemtype1; /定義運(yùn)算數(shù)棧的結(jié)點(diǎn)typedef struct /定義運(yùn)算數(shù)棧的類型selemtype1 *base; selemtype1 *top;sqstac

5、k1;void InitStack1(sqstack1 &s) /新建一個(gè)空運(yùn)算數(shù)棧s.base=(selemtype1 *)malloc(MAXNUM*sizeof(selemtype1); s.top=s.base; if(!s.base) printf("出錯(cuò):申請(qǐng)空間失??!n"); void Push1(sqstack1 &s,selemtype1 &e) /運(yùn)算數(shù)棧,入棧:插入元素e為新的棧頂元素 if(s.top-s.base>=MAXNUM) printf("出錯(cuò):表達(dá)式過長(zhǎng)!1n"); *s.top+ =e;

6、 void GetTop1(sqstack1 s,selemtype1 &e) /運(yùn)算數(shù)棧,用e返回棧頂元素e=*(s.top-1);void Popopnd1(sqstack1 &s,selemtype1 &e) /運(yùn)算數(shù)棧,退棧:刪除棧頂元素,并用e返回其值e=*-s.top;int stackempy1(sqstack1 s) /運(yùn)算數(shù)棧,若為空棧返回1,否則返回0if(s.top=s.base) return 1; else return 0;typedef char selemtype2; /定義運(yùn)算符棧的結(jié)點(diǎn)類型typedef struct /定義運(yùn)算符棧類

7、型selemtype2 *base; selemtype2 *top;sqstack2;void InitStack2(sqstack2 &s) /新建一個(gè)空運(yùn)算符棧s.base=(selemtype2 *)malloc(MAXNUM*sizeof(selemtype2); s.top=s.base; if(!s.base) printf("出錯(cuò):申請(qǐng)空間失??!n"); void Push2(sqstack2 &s,selemtype2 &e) /運(yùn)算符棧,入棧:插入元素e為新的棧頂元素 if(s.top-s.base>=MAXNUM) pri

8、ntf("出錯(cuò):表達(dá)式過長(zhǎng)!2n"); *s.top+ =e;void GetTop2(sqstack2 s,selemtype2 &e) /運(yùn)算符棧,用e返回棧頂元素e=*(s.top-1);void Popopnd2(sqstack2 &s,selemtype2 &e) /運(yùn)算符棧,退棧:刪除棧頂元素,并用e返回其值e=*-s.top;int stackempy2(sqstack2 s) /運(yùn)算符棧,若為空棧返回1,否則返回0if(s.top=s.base) return 1; else return 0;void priority(char c

9、,int &i) /確定運(yùn)算符優(yōu)先級(jí)if (c='*'|c='/'|c='%') i=2 ; else if (c='+'|c='-') i=1 ; else i=0;int compare(char a,char b) /比較棧頂元素運(yùn)算符與外部運(yùn)算符優(yōu)先級(jí)大小,外部?jī)?yōu)先級(jí)大則返回1,反之返回0int in,out; priority(a,in); priority(b,out); if(out>in) return 1; else return 0;void Operat(sqstack1 &am

10、p;OPND,sqstack2 &OPTR)int num1,num2,num; char c; Popopnd1(OPND,num2); Popopnd1(OPND,num1); 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

11、%num2;break; Push1(OPND,num); void Operatqianzhui(sqstack1 &OPND,sqstack2 &OPTR)int num1,num2,num; char c; Popopnd1(OPND,num1); Popopnd1(OPND,num2); Popopnd2(OPTR,c); switch(c) case '+':num=num1+num2;break; case '-':num=num1-num2;break; case '*':num=num1*num2;break; c

12、ase '/':num=num1/num2;break; case '%':num=num1%num2;break; Push1(OPND,num); void houzhuiqiuzhi(Lnode *p,int &e) /后綴表達(dá)式求值sqstack1 OPND; /運(yùn)算數(shù)棧 sqstack2 OPTR; /運(yùn)算符棧 int n; char c; p=p->next; InitStack1(OPND); InitStack2(OPTR); while(p) switch(p->data) case 1:n=p->data1; Pus

13、h1(OPND,n); break; case 2:c=p->data2; Push2(OPTR,c); Operat(OPND,OPTR); break; default:printf("結(jié)點(diǎn)有誤"); break; p=p->next; Popopnd1(OPND,n);e=n;void zhongzhui(Lnode *p) /中綴表達(dá)式求值sqstack1 OPND; /運(yùn)算數(shù)棧 sqstack2 OPTR; /運(yùn)算符棧 int n; char c,c2; Lnode *first; first=p; p=p->next; InitStack1(O

14、PND); InitStack2(OPTR); while(!stackempy2(OPTR)|p) while(p) switch(p->data) case 1:n=p->data1; Push1(OPND,n); break; case 2:c=p->data2; if(stackempy2(OPTR) Push2(OPTR,c); else switch(c) case '(': Push2(OPTR,c);break; case ')': GetTop2(OPTR,c2); while(c2!='(') Operat(

15、OPND,OPTR); GetTop2(OPTR,c2); Popopnd2(OPTR,c2); break; default: GetTop2(OPTR,c2); if(compare(c2,c) Push2(OPTR,c); else Operat(OPND,OPTR); Push2(OPTR,c); break; break; default: printf("結(jié)點(diǎn)有誤"); break; p=p->next; while(!stackempy2(OPTR) Operat(OPND,OPTR); Popopnd1(OPND,n); p=first->nex

16、t; while(p) if(p->data=1) printf("%d ",p->data1); if(p->data=2) printf("%c",p->data2); p=p->next; printf("=%d ",n);void houzhui(Lnode *p) /中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式sqstack2 OPTR; /運(yùn)算符棧 Lnode *r,*q,*head; int n; char c,c2; InitStack2(OPTR); p=p->next; q=(Lnode*)mal

17、loc(sizeof(struct Node); head=q; while(p) switch(p->data) case 1:n=p->data1; r=(Lnode*)malloc(sizeof(struct Node); q->next=r; q=q->next; q->data=1; q->data1=n; break; case 2:c=p->data2; if(stackempy2(OPTR) Push2(OPTR,c); else switch(c) case '(': Push2(OPTR,c);break; case

18、 ')': Popopnd2(OPTR,c2); while(c2!='(') r=(Lnode*)malloc(sizeof(struct Node); 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(struct Node); q->next=r; q=q

19、->next; q->data=2; q->data2=c2; GetTop2(OPTR,c2); Push2(OPTR,c); break; break; default: printf("結(jié)點(diǎn)有誤"); break; p=p->next; while(!stackempy2(OPTR) Popopnd2(OPTR,c2); r=(Lnode*)malloc(sizeof(struct Node); q->next=r; q=q->next; q->data=2; q->data2=c2; q->next=NULL;

20、q=head->next; while(q) if(q->data=1) printf("%d ",q->data1); if(q->data=2) printf("%c",q->data2); q=q->next; houzhuiqiuzhi(head,n); printf("=%d ",n);void qianzhuiqiuzhi(Lnode2 *p,int &e) /前綴表達(dá)式求值sqstack1 OPND; /運(yùn)算數(shù)棧 sqstack2 OPTR; /運(yùn)算符棧 int n; char

21、 c; Lnode2 *head; head=p; p=p->next; InitStack1(OPND); InitStack2(OPTR); while(p!=head) switch(p->data) case 1:n=p->data1; Push1(OPND,n); break; case 2:c=p->data2; Push2(OPTR,c); Operatqianzhui(OPND,OPTR); break; default:printf("結(jié)點(diǎn)有誤"); break; p=p->next; Popopnd1(OPND,n);e=n

22、;void qianzhui(Lnode *p) /中綴表達(dá)式轉(zhuǎn)化為前綴表達(dá)式sqstack2 OPTR; /運(yùn)算符棧 InitStack2(OPTR); int n; char c,c2; Lnode *first; Lnode2 *q,*head,*r,*head2,*s; first=p; p=p->next; q=(Lnode2*)malloc(sizeof(struct Node2); /建立存中綴表達(dá)式的雙向循環(huán)鏈表 head=q; while(p) r=(Lnode2*)malloc(sizeof(struct Node2); q->next=r; r->pri

23、or=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*)malloc(sizeof(struct Node2); /建立存前綴表達(dá)式的雙向循環(huán)鏈表 head2=s; while(q!=head) switch(q->data) case 1:n=q->data1; r=(Lnode2*)malloc(sizeof(struct Node

24、2); s->next=r; r->prior=s; s=s->next; s->data=1; s->data1=n; break; case 2:c=q->data2; if(stackempy2(OPTR) Push2(OPTR,c); else GetTop2(OPTR,c2); if(c2=')') Push2(OPTR,c); else switch(c) case ')':Push2(OPTR,c);break; case '(': Popopnd2(OPTR,c2); while(c2!=

25、9;)') r=(Lnode2*)malloc(sizeof(struct Node2); s->next=r; r->prior=s; s=s->next; s->data=2; s->data2=c2; Popopnd2(OPTR,c2); break; default: GetTop2(OPTR,c2); while(!compare(c2,c) Popopnd2(OPTR,c2); r=(Lnode2*)malloc(sizeof(struct Node2); s->next=r; r->prior=s; s=s->next; s

26、->data=2; s->data2=c2; GetTop2(OPTR,c2); Push2(OPTR,c); break; break; default:printf("結(jié)點(diǎn)有誤"); break; q=q->prior; while(!stackempy2(OPTR) Popopnd2(OPTR,c2); r=(Lnode2*)malloc(sizeof(struct Node2); s->next=r; r->prior=s; s=s->next; s->data=2; s->data2=c2; s->next=h

27、ead2; 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);int main() char n10; char c; int i,j,k,a,b,z,y,e; Lnode *p,*q,*first; i=0;e=1;a=0;b=1

28、;z=0;y=0; p=(Lnode*)malloc(sizeof(struct Node); first=p; printf("請(qǐng)輸入中綴表達(dá)式"); 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>&#

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論