biaodashiqiuzhi.cpp

数据结构表达式求值

 #define STACK_INT_SIZE 100
 #define STACKINCREMENT 10
 #define OVERFLOW -2
 #define ERROR 0
 #define OK 1
 #define ElemType int
 #define SElemType char
 #include<stdio.h>
 #include<stdlib.h>
 int flag=1;
struct SqStackTR{
      SElemType *base,*top;
      int  stacksize;
};                                      // struck type  define, char stack

struct SqStackND{
      ElemType *base,*top;
           int stacksize;
 };                                     // struck type  define  



 SElemType InitStackTR(SqStackTR *s){   //creat a empty stack s
     s->base=(SElemType *)malloc(STACK_INT_SIZE *sizeof(SElemType));
 if(!s->base)exit (OVERFLOW);            //memory distribuit failing
     s->top=s->base;
     s->stacksize=STACK_INT_SIZE;
  return OK;
}//InitStackTR

ElemType InitStackND(struct SqStackND *s){ //creat a empty stack s
   s->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType));
if(!s->base)exit (OVERFLOW);              //memory distribuit failing
   s->top=s->base;
   s->stacksize=STACK_INT_SIZE;
return OK;
}//InitStackND

 void PushTR( SqStackTR *s,SElemType e){  //insert e into the top of stack s
 if(s->top-s->base>=s->stacksize){        //stack is full
    s->base=(SElemType *)realloc( s->base,
   (s->stacksize+STACKINCREMENT) *sizeof(SElemType));
 if(!s->base) exit(OVERFLOW);             //memory distribuit failing
   s->top=s->base+s->stacksize;
   s->stacksize+=STACKINCREMENT;
 }
  *(s->top++)=e;
 }//PushTR      

void PushND(SqStackND *s,ElemType e){     //insert e into the top of stack s
 if(s->top-s->base==s->stacksize){        //stack is full
   s->base=(ElemType *)realloc( s->base,
  (s->stacksize+STACKINCREMENT) *sizeof(ElemType));
if(!s->base) exit(OVERFLOW);              //memory distribuit failing
   s->top=s->base+s->stacksize;
   s->stacksize+=STACKINCREMENT;
 }
   *(s->top++)=e;

 }//PushND   

SElemType PopTR( SqStackTR *s){
 //delete the top element ,return it's value with e
   SElemType e;
   if(s->top==s->base)
   return ERROR;
   e=*(--s->top);
   return e;
 }//PopTR                                    


ElemType PopND(struct SqStackND *s){
//delete the top element ,return it's value with e
 ElemType e; 
 if(s->top==s->base)
   return ERROR;
   e=*(--s->top);
   return e;
 }//PopND 


GetTopTR( SqStackTR  *s) {
    SElemType e;
   if(s->top==s->base)                     //the stack is empty
    return ERROR;
    e=*(s->top-1);
    return  e  ;
 }//GetTopTR

GetTopND(struct SqStackND *s){
    ElemType e;
    if(s->top==s->base)                     //the stack is empty
    return ERROR;
    e=*(s->top-1);
    return e  ;
 }//GetTopND

 


char precede(char op,char c)             //compair two char ,which one is preferential
{ char a;
  int pos_op;                            // return the result with  '<','>','='
  int pos_c;
  int i;
  char OP[7]={'+','-','*','/','(',')','#'};
  int precede[7][7]={
      1,1,2,2,2,1,1,
      1,1,2,2,2,1,1,
      1,1,1,1,2,1,1,
      1,1,1,1,2,1,1,
      2,2,2,2,2,3,0,
      1,1,1,1,0,1,1,
      2,2,2,2,2,0,3};

for(i=0;i<7;i++)
    {
      if(op==OP[i]) pos_op=i;
      if(c==OP[i]) pos_c=i;
    }
  switch(precede[pos_op][pos_c])         
    {
      case 1:  return '>';
      case 2:  return '<';
      case 3:  return '=';
      case 0:  return '0';
}

  return a;
}

ElemType  Operate(ElemType a,char theta,ElemType b)       //calculate a theta b 
{    ElemType z;
  switch(theta)
    {
      case '+':return a+b;
      case '-':return a-b;
      case '*':return a*b;
      case '/':if(b!=0)return a/b;  
      else printf("The divide number can't be zero ");
      return 0;
}
      return z;
}






int In(char c)
{
  int i=0;
  char OP[7]={'+','-','*','/','(',')','#'};
  while(i<7)
     if(c==OP[i++])
      return 1;
      return 0;

    }
ElemType EvaluateExpression()
{
   SqStackND *OPND;
   SqStackTR *OPTR;
   SElemType c,theta ,n  ;
    ElemType a,b,m,d,f;
   InitStackTR(OPTR);  
     PushTR(OPTR,'#');
   InitStackND(OPND);
   c=getchar();
  while(c!='#'||GetTopTR(OPTR)!='#')
    {
      if(In(c)!=1)
        { d=(int)c-48;
          PushND(OPND,d);
          c=getchar();
          while(In(c)!=1)
         { 
	    d=PopND(OPND);
	    f=(int)c-48;
	    d=d*10+f;
	    PushND(OPND,d);
	    c=getchar();
           }
          }

    else {  n=GetTopTR(OPTR);

	switch(precede(n,c))
	  {
	    case '<':
	      PushTR(OPTR,c);
	      c=getchar();
	      break;
	    case '=':
	      PopTR(OPTR);
	      c=getchar();
	      break;
	    case '>':
	      theta=PopTR(OPTR);
	          b=PopND(OPND);  
                  a=PopND(OPND);
	      PushND(OPND,Operate(a,theta,b));
              break;
	    case '0':
                   flag=0;
                   return 0;
           }
    }

}
   m= GetTopND(OPND);
   return m;
}

void main()
{
  ElemType i;
  printf("input a expression end with symbol #:\n");
  i=EvaluateExpression();
  if(flag==0)
   printf("The expression is illegal");
  else
  printf("\nThis expression's result is:%d \n",i);
  getchar();
  getchar();
}