中缀表达式求值实验报告
徐晨晖PB11005030 一、程序功能
简易的中缀表达式求值和中缀表达式转换成后缀表达式。
二、存储结构：栈
运算符栈：
typedef struct optr{
char elem;
struct optr *next;
}OPTRMode; //栈的结点类型
typedef OPTRMode* OPTRStack; //栈的头结点
运算数栈：
typedef struct opnd{
double elem;
struct opnd *next;
}OPNDMode; //栈的结点类型
typedef OPNDMode* OPNDStack; //栈的头结点
三、算法思想的描述
int main(){
OPTRStack OPTR;//定义运算符栈OPTR
InitStack_OPTR(OPTR);//初始化
OPNDStack OPND;//定义运算数栈OPND
InitStack_OPND(OPND);//初始化
double b,p,q;
int i,j=0,k=1,n;
char c,e,x,theta;
char f[100];
printf("==简易中缀表达式转换为后缀表达式，并求值==\n");
printf(" 1.运行\n 0.退出\n");
scanf("%d",&i);
while(i){
Push_OPTR(OPTR,'#');
printf("输入合法的中缀表达式，以'#'结束\n");
getchar();
j=0;
while((c=getchar())!='#'){
f[j]=c;
j++;
}
f[j]='#';n=j;
j=0;
printf("后缀表达式为：");
while(j<=n){
if(!isOperator(f[j])){//如果不是运算符
b=f[j]-48;
printf("%c",f[j]);
while(!isOperator(f[++j])&&f[j]!='#'){
b=b*10+(f[j]-48);
printf("%c",f[j]);
}
Push_OPND(OPND,b);//进运算数栈OPND
printf(" ");
}
else{//是运算符
GetTop_OPTR(OPTR,e);
while(e!=f[j]){
switch(Precede(e,f[j])){
case'<'://栈顶元素优先权低
Push_OPTR(OPTR,f[j]);
break;
case'='://脱括号并接受下一字符
Pop_OPTR(OPTR,x);
break;
case'>'://退栈并将运算结果出栈
Pop_OPTR(OPTR,theta);
printf("%c ",theta);
Pop_OPND(OPND,q); Pop_OPND(OPND,p);
Push_OPND(OPND,Operate(p,theta,q));
break;
}
if(OPTR->next==NULL||e=='(') e=f[j];
else GetTop_OPTR(OPTR,e);
}
j++;
}
}
GetTop_OPND(OPND,b);
printf("\n表达式的值=%lf\n",b);
printf(" 1.运行\n 0.退出\n");
scanf("%d",&i);
}
return(0);
}
四、各个函数名为：
运算符栈：
void InitStack_OPTR(OPTRStack &s);//初始化空栈
void Push_OPTR(OPTRStack &s,char e);//进栈
int GetTop_OPTR(OPTRStack s,char &e);//读栈顶
int Pop_OPTR(OPTRStack &s,char &e);//出栈
运算数栈：
void InitStack_OPND(OPNDStack &s);//初始化空栈
void Push_OPND(OPNDStack &s,double e);//进栈
int GetTop_OPND(OPNDStack s,double &e);//读栈顶
int Pop_OPND(OPNDStack &s,double &e);//出栈
其他：
char Precede(char a,char b);//比较算符优先级高低
double Operate(double a,char theta,double b);//计算
int isOperator(char c);//判断是否是运算符
五、测试与分析
本程序只适用与简易的表达式求值，只能对正整数进行运算。由于编程水平有限，时间紧，无法再进一步强化。
测试时：输入表达式（3+2-1）*6/3#
六、对实验和课程学习的体会和意见
在调试时，发现还是存在很简单的的问题。导致时间的浪费。
