expresion.cpp

数据结构课程的经典源码

#include<stdio.h>
#include <string.h>
#include <conio.h>

#define PLUS  0
#define MINUS 1
#define POWER 2
#define DIVIDE 3
#define LEFTP 4
#define RIGHP 5
#define STARTEND 6
#define DIGIT  7
#define POINT  8
  
#define NUM 7
#define NO  32767
#define STACKSIZE 20

char a[]={'+','-','*','/','(',')','#'};
int PriorityTable[7][7]={{ 1, 1,-1,-1,-1, 1, 1},
                         { 1, 1,-1,-1,-1, 1, 1},
			 { 1, 1, 1, 1,-1, 1, 1},
			 { 1, 1, 1, 1,-1, 1, 1},
                         {-1,-1,-1,-1,-1, 0,NO},
                         { 1, 1, 1, 1,NO, 1, 1},
                         {-1,-1,-1,-1,-1,NO, 0}
			 };   //规定：=为0,>为1,<为-1,空为NO
int menu(void);
void InputExpression(char str[])
 { int len;
   printf("Input expression string:\n");
   scanf("%s",str);
   len=strlen(str);
   str[len]='#';
   str[len+1]='\0';
   }
int GetCharType(char ch)
 {  int i;
    for(i=0;i<NUM;i++) if(ch==a[i]) return(i);
    if(ch>='0' && ch<='9') return(DIGIT);
    if(ch=='.') return(POINT);
    return(-1);
   }
int EXCUTE(char *str,double *Result)
 {
   int pp,strlength,topTr,topNd,CharType,OPTR[STACKSIZE];
   double number,temp,OPND[STACKSIZE];

   OPTR[0]=STARTEND;
   topTr=1;
   topNd=0;
   pp=0;
   while((str[pp]))
    { CharType=GetCharType(str[pp]);  //确定字符类型
      switch(CharType)
       { case -1:    //不是表达式中的字符，表达式有错
	    return(0);
	 case DIGIT:   //数字字符，实数的开始字符
	    number=0;
	    while(str[pp]>='0' && str[pp]<='9')  //处理实数的整数部分
	       { number=number*10+(str[pp]-48);
		 pp++;
		 }
	    if(str[pp]=='.') //遇到小数点
	       { temp=10.0;
		 pp++;
		 while(str[pp]>='0' && str[pp]<='9')  //处理实数的小数部分
		   { number=number+(str[pp]-48)/temp;
		     temp=temp*10;
		     pp++;
		     }
		   }
	      OPND[topNd]=number;
	      topNd++;
	      break;
	  case POINT:   //小数点，以小数点开头的实数
	      number=0;
	      temp=10.0;
	      pp++;
	      while(str[pp]>='0' && str[pp]<='9')
		{ number=number+(str[pp]-48)/temp;
		  temp=temp*10;
		  pp++;
		  }
	      OPND[topNd]=number;
	      topNd++;
	      break;
	  case PLUS:    //+
	  case MINUS:   //-
	  case POWER:   //*
	  case DIVIDE:  ///
	    switch(PriorityTable[OPTR[topTr-1]][CharType])
	      { case -1:
		   OPTR[topTr]=CharType;
		   topTr++;
		   pp++;
		   break;
		case 1:
		   if(topNd>1)
		     { switch(OPTR[topTr-1])
			 { case PLUS:
			     OPND[topNd-2]=OPND[topNd-2]+OPND[topNd-1];
			     break;
			   case MINUS:
			     OPND[topNd-2]=OPND[topNd-2]-OPND[topNd-1];
			     break;
			   case POWER:
			     OPND[topNd-2]=OPND[topNd-2]*OPND[topNd-1];
			     break;
			   case DIVIDE:
			     OPND[topNd-2]=OPND[topNd-2]/OPND[topNd-1];
			     break;
			   }
			topTr--;
			topNd--;
			}
		   else //表达式有错
		      return(0);
		   break;
		 }
	       break;
          case LEFTP:   //(
	       OPTR[topTr]=CharType;
	       topTr++;
	       pp++;
	       break;
	   case RIGHP:  //)
	       switch(OPTR[topTr-1])
		 { case PLUS:
		      if(topNd>1)
			{ OPND[topNd-2]=OPND[topNd-2]+OPND[topNd-1];
			  topTr--;
			  topNd--;
			  }
		      else  return(0); //表达式有错
		      break;
		   case MINUS:
		      if(topNd>1)
			{ OPND[topNd-2]=OPND[topNd-2]-OPND[topNd-1];
			  topTr--;
			  topNd--;
			  }
		      else  return(0);  //表达式有错
		      break;
		   case POWER:
		      if(topNd>1)
			{ OPND[topNd-2]=OPND[topNd-2]*OPND[topNd-1];
			  topTr--;
			  topNd--;
			  }
		      else  return(0);  //表达式有错
		      break;
		   case DIVIDE:
		      if(topNd>1)
			{ OPND[topNd-2]=OPND[topNd-2]/OPND[topNd-1];
			  topTr--;
			  topNd--;
			  }
		      else  return(0);  //表达式有错
		      break;
		   case LEFTP:
		      topTr--;
		      pp++;
		      break;
                   case STARTEND:
                      return(0);  //表达式有错
		   }
	       break;
	    case STARTEND:   //遇到表达式结束符
	       while(topTr>1)
		{ switch(OPTR[topTr-1])
		   { case PLUS:
		       if(topNd>1)
			 { OPND[topNd-2]=OPND[topNd-2]+OPND[topNd-1];
			   topTr--;
			   topNd--;
			   }
		       else  return(0);
		       break;
		     case MINUS:
		       if(topNd>1)
			 { OPND[topNd-2]=OPND[topNd-2]-OPND[topNd-1];
			   topTr--;
			   topNd--;
			   }
		       else  return(0);
		       break;
		     case POWER:
		       if(topNd>1)
			 { OPND[topNd-2]=OPND[topNd-2]*OPND[topNd-1];
			   topTr--;
			   topNd--;
			   }
		       else  return(0);
		       break;
		     case DIVIDE:
		       if(topNd>1)
			 { OPND[topNd-2]=OPND[topNd-2]/OPND[topNd-1];
			   topTr--;
			   topNd--;
			   }
		       else  return(0);
		       break;
		     default: return(0);
		     }
		   }
	       if(topNd==1)
		  { *Result=OPND[0];
		    return(1);
		   }
	       else  return(0);
	      }
	  }
   return(0);
   }
void main()
{ int num,flag;
  double result;
  char str[256];
  str[0]=0;
  while(1)
    { num=menu();
      switch(num)
       {
	 case 1:
	    InputExpression(str);
	    flag=0;
	    printf("%s\n",str);
	    getchar();
	    getchar();
	    break;
	 case 2:
	    if(str[0]==0)
	      { printf("Expresson  is Empty!");
		getchar();
		break;
		}
	     if(!EXCUTE(str,&result))
		{ printf("The expression has error!\n");
		  getchar();
                  }
             else
                { printf("calulation has finished!\n");
                  getchar();
                  flag=1;
                  }
	     break;
	 case 3:
	    if(flag)
	      { printf("#%s=%lf\n",str,result);
		getchar();
		getchar();
               }
	    break;
	 case 4:
	    break;
	 }
      if(num==4) break;
      }
  }
int menu(void)
  { int num;
    clrscr();
    printf("%20c1--input expression\n",' ');
    printf("%20c2--calculation expression\n",' ');
    printf("%20c3--print result\n",' ');
    printf("%20c4--Quit\n",' ');
    printf("         please select 1,2,3,4:");
      do{
	  scanf("%d",&num);
	  }while(num<1 || num>4);
    return(num);
    }