C语言实现中缀后缀前缀表达式相互转化并求值

1、1.问题描述（1）表达式求值问题 表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀式（如：+ 11 / * 22 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2. 数据结构设计（1）表达式求值问题 由于表达式中有字符与数字两种类型，故定义结点一个标志域data，标志结点存储的为字符data=2还是数

2、字data=1，再寻找结点中对应的存储位置，读取数字域data1,字符域data2。而在前缀表达式时，存在表达式逆序，因表达式类型不统一，用栈逆序极不方便，选择构建双向链表，存储表达式。typedef struct node /定义存储中缀表达式的结点类型int data; int data1; char data2; struct node *next;lnode; typedef struct node2 /定义存储前缀表达式的结点类型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） 选择表达式转换并求值方式。按“1”选择中缀表达式求值，如图1.4所示。图1.4（3）按“2”选择中缀表达式转变为后缀表达式并求值，如图1.5所示。图1.5（4） 按“3”选择中缀表达式转变为前缀表达式并求值，如图1.6所示。图1.6附录：源代码（1）表达式求值问题#include<stdio.h> #include<stdlib.h>#define maxnum 100typedef s

4、truct node /定义存储中缀表达式的结点类型int data; int data1; char data2; struct node *next;lnode; typedef struct node2 /定义存储前缀表达式的结点类型int data; int data1; char data2; struct node2 *next; struct node2 *prior;lnode2; typedef int selemtype1; /定义运算数栈的结点typedef struct /定义运算数栈的类型selemtype1 *base; selemtype1 *top;sqstac

5、k1;void initstack1(sqstack1 &s) /新建一个空运算数栈s.base=(selemtype1 *)malloc(maxnum*sizeof(selemtype1); s.top=s.base; if(!s.base) printf("出错：申请空间失败！n"); void push1(sqstack1 &s,selemtype1 &e) /运算数栈，入栈：插入元素e为新的栈顶元素 if(s.top-s.base>=maxnum) printf("出错：表达式过长！1n"); *s.top+ =e;

6、 void gettop1(sqstack1 s,selemtype1 &e) /运算数栈，用e返回栈顶元素e=*(s.top-1);void popopnd1(sqstack1 &s,selemtype1 &e) /运算数栈，退栈：删除栈顶元素，并用e返回其值e=*-s.top;int stackempy1(sqstack1 s) /运算数栈，若为空栈返回1，否则返回0if(s.top=s.base) return 1; else return 0;typedef char selemtype2; /定义运算符栈的结点类型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) /确定运算符优先级if (c='*'|c='/'|c='%') i=2 ; else if (c='+'|c='-') i=1 ; else i=0;int compare(char a,char b) /比较栈顶元素运算符与外部运算符优先级大小，外部优先级大则返回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; /运算数栈 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("结点有误"); break; p=p->next; popopnd1(opnd,n);e=n;void zhongzhui(lnode *p) /中缀表达式求值sqstack1 opnd; /运算数栈 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("结点有误"); 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) /中缀表达式转化为后缀表达式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("结点有误"); 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; /运算数栈 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("结点有误"); break; p=p->next; popopnd1(opnd,n);e=n

22、;void qianzhui(lnode *p) /中缀表达式转化为前缀表达式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); /建立存中缀表达式的双向循环链表 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); /建立存前缀表达式的双向循环链表 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("结点有误"); 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>&#