suansubiaodashiqiuzhi.c

严蔚敏的数据结构习题集后面试题上的算术表达式的求值程序。

#include<stdio.h>
#include<malloc.h>
#define STACK_INIT_SIZE 100
#define OK 1
#define ERROR 0
#define len sizeof(SNodeType)
typedef struct SNodeType{
	double data;
	struct SNodeType *next;
}SNodeType,*SLinkType;
typedef struct{
	SLinkType base;
	SLinkType top;
	int stacksize;
}SqStack;
int InitStack(SqStack *S)
{
	S->base=(SLinkType)malloc(STACK_INIT_SIZE*len);
	if(!S->base) return ERROR;
	S->top=S->base;
	S->stacksize=STACK_INIT_SIZE;
	return OK;
}
int Push(SqStack *S,double e)
{
	SLinkType p;
	p=(SLinkType)malloc(len);
	if(!p) return ERROR;
	p->next=S->top;
	S->top->data=e;
	S->top=p;
	return OK;
}
int Pop(SqStack *S,double *r)
{
	if(S->top==S->base) return ERROR;
	S->top=S->top->next;
	*r=S->top->data;
	return OK;
}
int GetTop(SqStack *S,double *e)
{
	if(S->top==S->base) return ERROR;
	*e=S->top->next->data;
	return OK;
}
char Precede(double c3,double c4)
{
	char c,c1,c2;
	c1=(char)c3;
	c2=(char)c4;
	switch(c1)
	{
	case '+': if(c2=='/'||c2=='*'||c2=='(') c='<';
		else c='>';break;
	case '-': if(c2=='/'||c2=='*'||c2=='(') c='<';
		else c='>';break;
	case '*': if(c2=='(') c='<';
		else c='>';break;
	case '/': if(c2=='(') c='<';
		else c='>';break;
	case '(': if(c2==')') c='=';
		else if(c2=='#');
		else c='<';break;
	case ')': if(c2=='(') ;
		else c='>';break;
	case '#': if(c2==')') ;
		else if(c2=='#') c='=';
		else c='<';break;
	}
	return c;
}
double Operate(double a,double theta,double b)
{
	char theta1;
	double answer;
	theta1=(char)theta;
	switch(theta1)
	{
	case '+': answer=a+b;break;
	case '-': answer=a-b;break;
	case '*': answer=a*b;break;
	case '/': answer=a/b;break;
	}
	return answer;
}
int In(double c)
{
	int e;
	if(c>=35&&c<=47&&(c!=46)) e=0;
	else e=1;
	return e;
}
void main()
{
   SqStack OPTR,OPND;
   double a,b,c1,e,x,theta,last,answer,g;
   double d=10;
   int flag=0;
   char c;
   InitStack(&OPTR);
   InitStack(&OPND);
   Push(&OPTR,'#');
   last='#';
   c=getchar();
   GetTop(&OPTR,&e);
   while(c!='#'||e!='#')
   {   
	   c1=(int)c;
	   if(In(c1))
	   {  
          if(c=='.') flag=1;
		  else
		  {
		   if(In(last))
		   {  
               last=c1;
               Pop(&OPND,&g);
			   if(flag==0)
			   {
			   g=g*10;
			   c1=c1-48;
			   }
			   else
			   {   
				   c1=c1-48;
				   c1=c1/a;
				   a=a*10;
			   }
			   g=g+c1;
			   Push(&OPND,g);
		   }
		   else
		   {   
			   flag=0;
			   a=10;
			   last=c1;
			   c1=c1-48;
			   Push(&OPND,c1);
		   }
		  }
		   c=getchar();
	   }
	   else
	   {
		   last=c1;
		   switch(Precede(e,c1))
		   {
		   case '<': Push(&OPTR,c1);c=getchar();break;
		   case '=': Pop(&OPTR,&x);c=getchar();break;
		   case '>': Pop(&OPTR,&theta);
			         Pop(&OPND,&b);
					 Pop(&OPND,&a);
					 Push(&OPND,Operate(a,theta,b));
					 break;
		   }
		   GetTop(&OPTR,&e);
	   }
   }
   GetTop(&OPND,&answer);
   printf("该表达式的结果:%f\n",answer);
}