c語(yǔ)言實(shí)現(xiàn)中綴,后綴,前綴表達(dá)式轉(zhuǎn)換并求值分析

1、c語(yǔ)言實(shí)現(xiàn)中綴,后綴,前綴表達(dá)式轉(zhuǎn)換并求值 九 #include<stdio.h> #include<stdlib.h>#define MAXNUM 100typedef 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

2、;Lnode2; typedef int selemtype1; /定義運(yùn)算數(shù)棧的結(jié)點(diǎn)typedef struct /定義運(yùn)算數(shù)棧的類型selemtype1 *base;selemtype1 *top;sqstack1;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)空間失?。"); void Push1(sqstack1 &am

3、p;amp;s,selemtype1 &e) /運(yùn)算數(shù)棧，入棧：插入元素e為新的棧頂元素 if(s.top-s.base>=MAXNUM)printf("出錯(cuò)：表達(dá)式過(guò)長(zhǎng)！1n");*s.top+ =e; 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;

4、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)算符棧類型selemtype2 *base;selemtype2 *top;sqstack2;void InitStack2(sqstack2 &s) /新建一個(gè)空運(yùn)算符棧s.base=(selemtype2 *)malloc(MAXNUM*sizeof(selemtype2);s.top=s.ba

5、se;if(!s.base) printf("出錯(cuò)：申請(qǐng)空間失??！n"); void Push2(sqstack2 &s,selemtype2 &e) /運(yùn)算符棧，入棧：插入元素e為新的棧頂元素 if(s.top-s.base>=MAXNUM)printf("出錯(cuò)：表達(dá)式過(guò)長(zhǎng)！2n");*s.top+ =e;void GetTop2(sqstack2 s,selemtype2 &e) /運(yùn)算符棧，用e返回棧頂元素e=*(s.top-1);void Popopnd

6、2(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,int &i) /確定運(yùn)算符優(yōu)先級(jí)if (c='*'|c='/'|c='%') i=2 ;else if (c=&am

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

8、um2);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%num2;break;Push1(OPND, num); void O

9、peratqianzhui(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;case '

10、/':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->da

11、ta1;Push1(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;I

12、nitStack1(OPND);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);whil

13、e(c2!='(')Operat(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);Pop

14、opnd1(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);void houzhui(Lnode *p) /中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式sqstack2 OPTR; /運(yùn)算符棧Lnode *r,*q

15、,*head;int n;char c,c2;InitStack2(OPTR);p=p->next;q=(Lnode*)malloc(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(s

16、tackempy2(OPTR) Push2(OPTR,c);else switch(c) case '(': Push2(OPTR,c);break;case ')': 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;d

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

18、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;q=head->next;while(q)if(q->data=1) printf("%d ",q->data1);if(q->data=2) printf("%c"

19、,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 c;Lnode2 *head;head=p;p=p->next;InitStack1(OPND);InitStack2(OPTR);while(p!=head)switch(p-&gt

20、;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;void qianzhui(Lnode *p) /中綴表達(dá)式轉(zhuǎn)化為前綴表達(dá)式sqstack2 OPTR; /運(yùn)算符棧InitStack2(OPTR);int n;char c,c2;Ln

21、ode *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->prior=q;q=q->next;q->data=p->data;q->data1=p->data1;q->d

22、ata2=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*)ma lloc(sizeof(struct Node2);s->next=r;r->prior=s;s=s->next;s-&a

23、mp;gt;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!=')') r=(Ln

24、ode2*)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->ne

25、xt;s->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

26、->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);int main(

27、) 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;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 '

28、+': case '-': case '*': case '/': case '%': case '(': case ')': case 'n': if(n0>'0'&&n0<='9') q=(Lnode*)malloc(sizeof(struct Node);p->next=q;p=p->next;for(k=0;k<i;k+) for(j=0;j<=i-k-2;j+)e=e*10; a=a+(nk-'0')*e;e=1;nk='0'p-&