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

. . . .
1.问题描述
（1）表达式求值问题
表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*(7-4)/3。中缀式的计算按运算符的优先级与括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4 - * 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）按提示输入中缀表达式，如图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 100
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;

typedef int selemtype1; //定义运算数栈的结点

typedef struct //定义运算数栈的类型
{selemtype1 *base;
selemtype1 *top;
}sqstack1;

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("出错：表达式过长！1\n");
*s.top++ =e;
}

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，否则返回0
{if(s.top==s.base) return 1;
else return 0;
}

typedef char selemtype2; //定义运算符栈的结点类型

typedef struct //定义运算符栈类型
{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)
printf("出错：表达式过长！2\n");
*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，否则返回0
{if(s.top==s.base) 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(struct Node));
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;
}

20 / 20