#include<stdio.h>
#include<iostream.h>
#include <math.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAXN 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int status;
typedef struct {
char *base,*top;
int stacksize;
}sqstack_sign; //运算符栈的定义
typedef struct{
float *base,*top;
int stacksize;
}sqstack_num; //运算数栈的定义
int isp(char a)
{//栈内优先数
switch(a)
{case'*':
case'/':return(2);
case'+':
case'-':return(1);
case'(':return(0);
case'#':return(-1);
}
};
int icp(char a)
{//栈外优先数
switch(a)
{case'*':
case'/':return(2);
case'+':
case'-':return(1);
case'(':return(3);
}
};
status initstack1(sqstack_sign &s)
{//栈的初始化
s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));
if(!s.base)exit(OVERFLOW);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE; return OK;
};
status gettop1(sqstack_sign s, char &e)
{//取栈顶元素
if(s.top==s.base)return ERROR;
e=*(s.top-1); return OK;
};
status push1(sqstack_sign &s,char e)
{//进栈
if(s.top-s.base>=s.stacksize)
{
s.base=(char*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char));
if(!s.base)exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;
}
*s.top++=e; return OK;
};
status pop1(sqstack_sign &s,char &e)
{//出栈
if(s.top==s.base)return ERROR;
e=*--s.top; return OK;
};
status initstack2(sqstack_num &s)
{//栈的初始化
s.base=(float*)malloc(STACK_INIT_SIZE*sizeof(float));
if(!s.base)exit(OVERFLOW);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE; return OK;
};
status gettop2(sqstack_num s, float &e)
{//取栈顶元素
if(s.top==s.base)return ERROR;
e=*(s.top-1); return OK;
};
float push2(sqstack_num &s,float e)
{//进栈
if(s.top-s.base>=s.stacksize){
s.base=(float*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(float));
if(!s.base)exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;
}
*s.top++=e; return OK;
};
float pop2(sqstack_num &s,float &e)
{//出栈
if(s.top==s.base)return ERROR;
e=*--s.top; return OK;
};
status mid_to_pos(char mid_e[],char pos_e[])
{//中缀表达式转换后缀表达式
int i,j,k;
char c,ea,eb,ec;
sqstack_sign optr;
initstack1(optr);ec='#';
push1(optr,ec); //optr栈的初始化，栈底为#
i=0;j=0;
c=mid_e[0];
while(c!='#'&& i<MAXN)
{//k指示是否是运算数
if((c>='0'&&c<='9')||c=='.'){pos_e[i++]=c;k=0;}
else{
if(c==')')
{//遇")"则一直退到"("
pos_e[i++]=' '; gettop1(optr,ea);
while(ea!='(')
{
pop1(optr,eb); pos_e[i++]=eb;pos_e[i++]=' ';k=1;
gettop1(optr,ea);
}
pop1(optr,eb);
}//else if
else{
if(i>1&&k==0)pos_e[i++]=' ';
gettop1(optr,ea);
while(isp(ea)>=icp(c))
{//比较优先级
pop1(optr,eb);gettop1(optr,ea);
pos_e[i++]=eb;pos_e[i++]=' ';k=1;
}
push1(optr,c);pos_e[i++]=' ';
}
}
c=mid_e[++j];
}
gettop1(optr,ea);
while(ea!='#')
{//退栈到栈底
pos_e[i++]=' ';pop1(optr,eb);pos_e[i++]=eb; gettop1(optr,ea);
}
if(i==MAXN)return(OVERFLOW);
else pos_e[i++]=' ';pos_e[i]='#';
return OK;
}
float evaluate(char pos_e[])
{//后缀表达式求值
int i,j,k,n,flag;
float m,e,ta,tb,d,t;float *p;
char c;
sqstack_num opnd;
initstack2(opnd); //opnd栈的初始化
i=j=n=0;flag=0;
c=pos_e[0];
while(c!='#')
{
if(c==' ')
{
if(j>=2) //把字符转化为实数
{ m=0;k=j;
while(j>0)
{
pop2(opnd,e);
m+=e*(float)pow(10,k-j);j--;
}
m=m/(float)pow(10,n);
push2(opnd,m);
}
else j=0;
n=0;flag=0; //flag指示小数点的起始，n指示小数点后的位数
}
else{
if((c>='0'&&c<='9')||c=='.')
{ if(c=='.')flag=1;
else
{ if(flag==1)n++;
d=(float)(c-'0');push2(opnd,d);j++;
}
}
else
{//遇运算符则取数进行运算
pop2(opnd,ta);pop2(opnd,tb);
if(c=='*')t=ta*tb;
if(c=='/'){if(ta==0)return ERROR;else t=tb/ta;}
if(c=='+')t=ta+tb;
if(c=='-')t=tb-ta;
push2(opnd,t);
}
} p=opnd.base;while(p<opnd.top)printf("%f",*p++);printf("\n");
c=pos_e[++i];
}
gettop2(opnd,e);
return e;
};
void main()
{
int i,j;
float m;
char mid_e[MAXN],pos_e[MAXN],c;
printf("请输入实数求值表达式，只包含加减乘除运算( 以#为结束标志)：\n");
for(i=0;;i++)
{ scanf("%c",&mid_e[i]);
if(i==MAXN){ printf("表达式太长\n"); exit(OVERFLOW);}
if(mid_e[i]=='#')break;
}
printf("你输入的表达式是：");
j=0;
while(j<=i)printf("%c",mid_e[j++]);
printf("\n");
mid_to_pos(mid_e,pos_e);
c=pos_e[0];i=0; //打印后缀表达式
printf("转化成的后缀表达式是：");
while(c!='#'){printf("%c",pos_e[i++]);c=pos_e[i];}
printf("%c\n",pos_e[i]);
printf("运算数栈的变化过程：");
m=evaluate(pos_e);
printf("运算结果是：%f\n",m);
}
评论0