C語言實現(xiàn)中綴、后綴、前綴表達式 相互轉(zhuǎn)化并求值

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

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

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

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

5、k1;void InitStack1(sqstack1 &s) /新建一個空運算數(shù)棧s.base=(selemtype1 *)malloc(MAXNUM*sizeof(selemtype1); s.top=s.base; if(!s.base) printf("出錯：申請空間失?。"); void Push1(sqstack1 &s,selemtype1 &e) /運算數(shù)棧，入棧：插入元素e為新的棧頂元素 if(s.top-s.base>=MAXNUM) printf("出錯：表達式過長！1n"); *s.top+ =e;

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

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

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

9、,int &i) /確定運算符優(yōu)先級if (c='*'|c='/'|c='%') i=2 ; else if (c='+'|c='-') i=1 ; else i=0;int compare(char a,char b) /比較棧頂元素運算符與外部運算符優(yōu)先級大小，外部優(yōu)先級大則返回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) /后綴表達式求值sqstack1 OPND; /運算數(shù)棧 sqstack2 OPTR; /運算符棧 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é)點有誤"); break; p=p->next; Popopnd1(OPND,n);e=n;void zhongzhui(Lnode *p) /中綴表達式求值sqstack1 OPND; /運算數(shù)棧 sqstack2 OPTR; /運算符棧 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é)點有誤"); 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) /中綴表達式轉(zhuǎn)化為后綴表達式sqstack2 OPTR; /運算符棧 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é)點有誤"); 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) /前綴表達式求值sqstack1 OPND; /運算數(shù)棧 sqstack2 OPTR; /運算符棧 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é)點有誤"); break; p=p->next; Popopnd1(OPND,n);e=n

22、;void qianzhui(Lnode *p) /中綴表達式轉(zhuǎn)化為前綴表達式sqstack2 OPTR; /運算符棧 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); /建立存中綴表達式的雙向循環(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); /建立存前綴表達式的雙向循環(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é)點有誤"); 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("請輸入中綴表達式"); 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>&#