表达式求值.cpp.txt

表达式求值以字符序列的形式从终端输入语法正确的、不含变量的数据表达式。利用教科书表3.1给出的算符优先关系

#include<stdio.h>

#include<iostream.h>

#include <math.h>

#include<stdlib.h>

#define stack_init_size 100

#define stackincrement 10

#define maxlen 100

#define ok 1

#define error 0

#define overflow -2

typedef int status;

void main();

typedef struct {

         char *base,*top;

         int stacksize;

}sqstack1;//运算符栈的定义

typedef struct{

         float *base,*top;

         int stacksize;

}sqstack2;//运算数栈的定义

int isp(char a){//栈内优先数

         int e;

         if(a=='*'||a=='/') e=2;

         if(a=='+'||a=='-') e=1;

         if(a=='(') e=0;

         if(a=='#') e=-1;

         return e;

};

int icp(char a){//栈外优先数

         int e;

         if(a=='*'||a=='/')e=2;

         if(a=='+'||a=='-')e=1;

         if(a=='(')e=3;

         return e;

};

status initstack1(sqstack1 &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(sqstack1 s, char &e){//取栈顶元素

         if(s.top==s.base)return error;

         e=*(s.top-1); return ok;

};

status push1(sqstack1 &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(sqstack1 &s,char &e){//出栈

         if(s.top==s.base)return error;

         e=*--s.top; return ok;

};

status  initstack2(sqstack2 &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(sqstack2 s, float &e){//取栈顶元素

         if(s.top==s.base)return error;

         e=*(s.top-1); return ok;

};

float push2(sqstack2 &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(sqstack2 &s,float &e){//出栈

         if(s.top==s.base)return error;

         e=*--s.top; return ok;

};

status postfix(char la[],char lb[]){

         int i,j,k; 

         char c,ea,eb,ec;

         sqstack1 optr;

         initstack1(optr);ec='#';

         push1(optr,ec);//optr栈的初始化，栈底为#

         i=0;j=0;

         c=la[0];

         while(c!='#'&& i<maxlen){//k指示是否是运算数

        if((c>='0'&&c<='9')||c=='.'){lb[i++]=c;k=0;}

                   else{ 

                            if(c==')'){//遇")"则一直退到"("

                                     lb[i++]=' '; gettop1(optr,ea);

                                     while(ea!='('){

                                               pop1(optr,eb); lb[i++]=eb;lb[i++]=' ';k=1;

                                              gettop1(optr,ea);

                }

                                     pop1(optr,eb);

                            }//else if

                            else{

                                     if(i>1&&k==0)lb[i++]=' ';

                                     gettop1(optr,ea);

                                     while(isp(ea)>=icp(c)){//比较优先级

                                               pop1(optr,eb);gettop1(optr,ea);

                                               lb[i++]=eb;lb[i++]=' ';k=1;

                                     }

                                     push1(optr,c);lb[i++]=' ';

                            }

                   }

                            c=la[++j];

         }

         gettop1(optr,ea);

         while(ea!='#'){//退栈到栈底

                   lb[i++]=' ';pop1(optr,eb);lb[i++]=eb; gettop1(optr,ea);

         }

   if(i==maxlen)return(overflow);

         else lb[i++]=' ';lb[i]='#';

         return ok;

}

 

 

float eval(char lb[])

{

         int i,j,k,n,flag;

         float m,e,ta,tb,d,t;float *p;

         char c;

         sqstack2 opnd;

         initstack2(opnd);//opnd栈的初始化

         i=j=n=0;flag=0;

         c=lb[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=lb[++i];

         }

                   gettop2(opnd,e);

                   return e;

};

 

void main(){

int i,j;

float m;

char la[maxlen],lb[maxlen],c;

printf("%s","请输入实数求值表达式，只包含加减乘除运算( 以#为结束标志)：\n");

for(i=0;;i++){ scanf("%c",&la[i]);

              if(i==maxlen){ printf("表达式太长\n"); exit(overflow);} 

                              if(la[i]=='#')break; 

}

printf("你输入的表达式是：");

j=0;while(j<=i)printf("%c",la[j++]);printf("\n");postfix(la,lb);

c=lb[0];i=0;//打印后缀表达式

printf("转化成的后缀表达式是：");

while(c!='#'){printf("%c",lb[i++]);c=lb[i];}

printf("%c\n",lb[i]);

printf("运算数栈的变化过程：");

m=eval(lb);  

printf("运算结果是：%f\n",m);  

};