1.问题描述（1）表达式求值问题表达式是数据运算的基本形式。
人们的书写习惯是中缀式，如：11+22*(7-4)/3 。
中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。
表达式还有后缀式（如：2274-*3/11+）和前缀式（如： + 11 / * 22–7 4 3）。
后缀表达式和前缀表达式中没有括号，给计算带来方便。
如后缀式计算时按运算符出现的先后进行计算。
本设计的主要任务是进行表达式形式的变换及不相同形式的表达式计算。
2.数据结构设计（ 1）表达式求值问题由于表达式中有字符与数字两各种类，故定义结点一个标志域 data ，标志结点储藏的为字符 data=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;}Lnode2;3. 运行、测试与解析（ 1）表达式求值问题（1）按提示输入中缀表达式，以下列图。
如输入中缀表达式不正确，提示输入有误，如图 , 所示。
图图图（2）选择表达式变换并求值方式。
按“1”选择中缀表达式求值，以下列图。
图（3）按“ 2”选择中缀表达式转变为后缀表达式并求值，以下列图。
图（4）按“ 3”选择中缀表达式转变为前缀表达式并求值，以下列图。
图附录：源代码（ 1）表达式求值问题#include<>#include<>#define MAXNUM 100typedef 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;}Lnode2;typedef int selemtype1;//定义运算数栈的结点typedef struct //定义运算数栈的种类{selemtype1 *base;selemtype1*top; }sqstack1;void InitStack1(sqstack1 &s) //新建一个空运算数栈{=(selemtype1 *)malloc(MAXNUM*sizeof(selemtype1));=;if(! printf("出错：申请空间失败！\n");}void Push1(sqstack1 &s,selemtype1 &e)//运算数栈，入栈：插入元素 e 为新的栈顶元素{ if printf("出错：表达式过长！1\n");*++=e;}void GetTop1(sqstack1 s,selemtype1 &e) //运算数栈，用e返回栈顶元素{e=*;}void Popopnd1(sqstack1 &s,selemtype1 &e) // 运算数栈，退栈：删除栈顶元素，并用 e 返回其值{e=*;}int stackempy1(sqstack1 s) // 运算数栈，若为空栈返回 1，否则返回 0 {if== return 1;else return 0;}typedef char selemtype2;//定义运算符栈的结点种类typedef struct //定义运算符栈种类{selemtype2 *base;selemtype2*top; }sqstack2;void InitStack2(sqstack2 &s) //新建一个空运算符栈{=(selemtype2 *)malloc(MAXNUM*sizeof(selemtype2));=;if(! printf("出错：申请空间失败！\n");}void Push2(sqstack2 &s,selemtype2 &e)//运算符栈，入栈：插入元素 e 为新的栈顶元素{ if printf("出错：表达式过长！2\n");*++=e;}void GetTop2(sqstack2 s,selemtype2 &e) //运算符栈，用e返回栈顶元素{e=*;}void Popopnd2(sqstack2 &s,selemtype2 &e) // 运算符栈，退栈：删除栈顶元素，并用 e 返回其值{e=*;}int stackempy2(sqstack2 s) // 运算符栈，若为空栈返回 1，否则返回 0 {if== return 1;else return 0;}void priority(char c,int &i)//确定运算符优先级{if (c=='*'||c=='/'||c=='%') i=2 ;else if (c=='+'||c=='-') i=1 ;else i=0;}int compare(char a,char b) //比较栈顶元素运算符与外面运算符优先级大小，外面优先级大则返回1，反之返回 0{int 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,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%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;case '/':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;Push1(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(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);while(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("结点有误");break;}p=p->next;}while(!stackempy2(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);}void houzhui(Lnode*p)//中缀表达式转变为后缀表达式{sqstack2 OPTR; //运算符栈Lnode *r,*q,*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(stackempy2(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;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->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;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 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;}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->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*)malloc(sizeof(struct Node2));//成立存前缀表达式的双向循环链表head2=s;while(q!=head){switch(q->data){case 1:n=q->data1;r=(Lnode2*)malloc(sizeof(struct Node2));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!=')'){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->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=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(){ char n[10];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("请输入中缀表达式 ");do{ c = getchar();if('0'<=c&&c<='9'){ n[i]=c;i++;}else{ switch (c){ case '+':case '-':case '*':case '/':case '%':case '(':case ')':case '\n':{ if(n[0]>'0'&&n[0]<='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+(n[k]-'0')*e;e=1;n[k]='0';}p->data=1;p->data1=a;i=0;a=0;}if(c!='\n'){ if(p->data==2){ if(p->data2!=')'&&c!='(')b=0;}q=(Lnode*)malloc(sizeof(struct Node));p->next=q;p=p->next;p->data=2;p->data2=c;if(c=='(') z++;if(c==')') y++;}}default:if(c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!='%'&&c!='\n'&&c!='('&&c!=')')b=0;}}}while (c != '\n');if(z!=y) b=0;p->next=NULL;if(b==0)printf("输入中缀表达式有误 ");else{printf(" 输入 1 中缀表达式求值，输入 2 后缀表达式求值，输入 3 前缀表达式求值 ");scanf("%d",&b);if(b==1) zhongzhui(first); if(b==2) houzhui(first); if(b==3) qianzhui(first); }return 1;}。
