suan_shu_biao_da_shi_qiu_zhi.txt

1

#include<stdlib.h>
#include<iostream.h>
#include<stdio.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct{
	//运算符栈
	char *base;
	char *top;
	int stacksize;
}SqStack_tr;

typedef struct{
	//操作数栈
	int *base;
	int *top;
	int stacksize;
}SqStack_nd;

char InitStack_tr(SqStack_tr&S){
	//构造运算符栈
	S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));
	if(!S.base)exit(-2);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}//InitStack_tr

char Push_tr(SqStack_tr &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(-2);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*(S.top++)=e;
	return OK;
}//Push_tr

char GetTop_tr(SqStack_tr S,char &e){
	//取运算符栈定元素
	if(S.top==S.base)
		return 0;
	e=*(S.top-1);
	return OK;
}//Gettop_tr

char Pop_tr(SqStack_tr &S,char &e){
	//运算符出栈
	if(S.top==S.base)
		return 0;
	--S.top;
	e=*(S.top);
	return OK;
}//Pop_tr

int InitStack_nd(SqStack_nd &S){
	//构造操作数栈
	S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));
	if(!S.base)exit(-2);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}//InitStack_nd

int Push_nd(SqStack_nd &S,int e){
	//操作数进栈
	if(S.top-S.base>=S.stacksize){
		S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
		if(!S.base)exit(-2);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*(S.top++)=e;
	return OK;
}//Push_nd

int GetTop_nd(SqStack_nd S,int &e){
	//取操作数栈顶元素
	if(S.top==S.base)
		return 0;
	e=*(S.top-1);
	return OK;
}//Gettop_nd

int Pop_nd(SqStack_nd &S,int &e){
	//操作数出栈
	if(S.top==S.base)
		return 0;
	--S.top;
	e=*(S.top);
	return OK;
}//Pop_nd

char Precede(char t1,char t2){  
	 //根据教科书表3.1，判断两符号的优先关系 
	 char f;
     switch(t2)
	 {
	    case '+':
        case '-':if(t1=='('||t1=='#')
                   f='<';
                 else
                   f='>';
                 break;
        case '*':
        case '/':if(t1=='*'||t1=='/'||t1==')')
                   f='>';
                 else
                   f='<';
                 break;
        case '(':if(t1==')')
              {
                  printf("ERROR1\n");
                  exit(ERROR);
              }
                 else
                  f='<';
                 break;
        case ')':switch(t1)
              {
                 case '(':f='=';
                         break;
                 case '#':printf("ERROR2\n");
                         exit(ERROR);
                 default: f='>';
              }
                 break;
       case '#':switch(t1)
              {
                 case '#':f='=';
                         break;
                 case '(':printf("ERROR3\n");
                         exit(ERROR);
                 default: f='>';
              }
	 }
   return f;
 }

 char In(char c)
 { // 判断c是否为运算符 
   switch(c)
   {
     case'+':
     case'-':
     case'*':
     case'/':
     case'(':
     case')':
     case'#':return TRUE;
     default:return FALSE;
   }
 }

 int Operate(int a,char theta,int b)
 { //进行二元运算
   int c;
   switch(theta)
   {
     case'+':c=a+b;
             break;
     case'-':c=a-b;
             break;
     case'*':c=a*b;
             break;
     case'/':
		 if(b==0){
			 printf("除数不能为零\n");
			 exit(-2);
			 break;
		 }
		 else
			 c=a/b;
		 break;
   }
   return c;
 }

 int EvaluateExpression() // 算法3.4 
 { // 算术表达式求值的算符优先算法。
   //设OPTR和OPND分别为运算符栈和运算数栈 
   SqStack_tr OPTR;
   SqStack_nd OPND;
   int a,b,d;
   char c,x,theta;
   InitStack_tr(OPTR);
   Push_tr(OPTR,'#');
   InitStack_nd(OPND);
   c=getchar();
   GetTop_tr(OPTR,x);

   bool preIsD=false;      //判断输入的是不是二位数
   int e;

   while(c!='#'||x!='#')
   {
	   if(!In(c))
	   {
		   // 不是7种运算符之一
		   int num=c-'0';
		   if(preIsD)
		   {
			   Pop_nd(OPND,e);
			   num=e*10+num;
		   }
		   preIsD=true;
		   Push_nd(OPND,num);
		   c=getchar();
	   }
	   else
	   {
		   preIsD=false;
		   switch(Precede(x,c))
		   {
		   case'<':Push_tr(OPTR,c); // 栈顶元素优先权低 
			   c=getchar();
			   break;
		   case'=':Pop_tr(OPTR,x); // 脱括号并接收下一字符 
			   c=getchar();
			   break;
		   case'>':Pop_tr(OPTR,theta); // 退栈并将运算结果入栈 
			   Pop_nd(OPND,b);
			   Pop_nd(OPND,a);
			   Push_nd(OPND,Operate(a,theta,b));
			   break;
		   }
	   }
	   GetTop_tr(OPTR,x);
   }
   GetTop_nd(OPND,d);
   return d;
 }

void main()
{
	int i;
	printf("请输入算术表达式，并以'#'结束\n");
	i=EvaluateExpression();
	printf("输出算术表达式的结果：%d\n",i);
	system("pause");
}