express.cpp

表达式求值

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

#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define STACK_INIT_SIZE	80
#define	STACKINCREMENT 10


typedef int Status;
typedef int FLAG;
typedef char CElemType;
typedef float FElemType;

typedef struct{
	CElemType *  base;
	CElemType *  top;
	int stacksize;
} CSqStack;


typedef struct{
	FElemType *  base;
	FElemType *  top;
	int stacksize;
} FSqStack;


CSqStack * InitCStack(void);
FSqStack * InitFStack(void);
CElemType GetTopC(CSqStack *s);
FElemType GetTopF(FSqStack *s);
CSqStack * PushC(CSqStack *s,CElemType e);
FSqStack * PushF(FSqStack *s,FElemType e);
CElemType PopC(CSqStack *s);
FElemType PopF(FSqStack *s);

/*````````````````````````````运算符栈基本操作``````````````````````````````````*/
CSqStack * InitCStack(void)
{
	CSqStack * s=NULL;
	s=(CSqStack *)malloc(sizeof(CSqStack));
	s->base = ( CElemType * )malloc(STACK_INIT_SIZE*sizeof(CElemType));
	if(!s->base) 
	{
		printf( "Memory error in Initializing stack.\n" );return NULL;
	}
	s->top = s->base;
	s->stacksize = STACK_INIT_SIZE;
	return s;
}

CElemType GetTopC(CSqStack *s)
{
	CElemType e;
 	if (s->top==s->base)
	{
		printf( "Empty stack,can't Get top.\n" );
        return ERROR;
	}
 	e=*(s->top-1);
 	return e;
}

CSqStack * PushC(CSqStack *s,CElemType e)
{
	if (s->top-s->base>=s->stacksize)
	{
		s->base=(CElemType * )realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(CElemType));
		if (!s->base)
		{
			printf( "Memory error in Initializing stack.\n" );return NULL;
		}
		s->top = s->base + s->stacksize;
		s->stacksize+=STACKINCREMENT;
	}
	*(s->top++) = e;
	return s;
}

CElemType PopC(CSqStack *s)
{
	CElemType e;
	if(s->top==s->base)
		return ERROR;
	e = *(--s->top);
		return e;
}

void Print_CSqStack(CSqStack * s)
{
	CElemType * p=s->base;
	printf("运算符栈元素为：");
	while(p!= s->top)
	{
		printf("%c",* p);
        p++;
	}
	printf("\n");
}


/*``````````````````````````````````````````运算数栈基本操作``````````````````````````````````*/
FSqStack * InitFStack(void)
{
	FSqStack *s=NULL;
	s=(FSqStack *)malloc(sizeof(FSqStack));
	s->base = ( FElemType * )malloc(STACK_INIT_SIZE*sizeof(FElemType));
	if(!s->base) 
	{
		printf( "Memory error in Initializing stack.\n" );return NULL;
	}
	s->top = s->base;
	s->stacksize = STACK_INIT_SIZE;
	return s;
}

FElemType GetTopF(FSqStack *s)
{
	FElemType e;
 	if (s->top==s->base)
	{
		printf( "Empty stack,can't Get top.\n" );
        return ERROR;
	}
 	e=*(s->top-1);
 	return e;
}

FSqStack * PushF(FSqStack *s,FElemType e)
{
	if (s->top-s->base>=s->stacksize)
	{
		s->base=(FElemType * )realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(FElemType));
		if (!s->base)
		{
			printf( "Memory error in Initializing stack.\n" );return NULL;
		}
		s->top = s->base + s->stacksize;
		s->stacksize+=STACKINCREMENT;
	}
	*(s->top++) = e;
	return s;
}

FElemType PopF(FSqStack *s)
{
	FElemType e;
	if(s->top==s->base)
		return ERROR;
	e = *(--s->top);
		return e;
}

void Print_FSqStack(FSqStack * s)
{
	FElemType * p=s->base;
	printf("运算数栈元素为：");
	while(p!=s->top)
	{
		printf("%-7.2f",* p);
        p++;
	}
	printf("\n");
}


/*``````````````````````````判断接收字符是否为运算符```````````````````````````*/
FLAG In(CElemType e)
{
	int i;
    CElemType operator_set[8] = {'+','-','*','/','(', ')','^','#'};
    for( i = 0; i < 8; i++ )
            if( operator_set[ i ] == e )
                    return OK;
    return ERROR;
}


/*```````````````````````````````比较运算符优先级``````````````````````````````````*/
CElemType Precede(char m,char n)
{
	if((m=='+'&&n=='+')||(m=='-'&&n=='+')||(m=='*'&&n=='+')||(m=='/'&&n=='+')||(m==')'&&n=='+')||
		(m=='+'&&n=='-')||(m=='-'&&n=='-')||(m=='*'&&n=='-')||(m=='/'&&n=='-')||(m==')'&&n=='-')||
		(m=='*'&&n=='*')||(m=='/'&&n=='*')||(m==')'&&n=='*')||
		(m=='*'&&n=='/')||(m=='/'&&n=='/')||(m==')'&&n=='/')||
		(m=='+'&&n==')')||(m=='-'&&n==')')||(m=='*'&&n==')')||(m=='/'&&n==')')||(m==')'&&n==')')||
		(m=='+'&&n=='#')||(m=='-'&&n=='#')||(m=='*'&&n=='#')||(m=='/'&&n=='#')||(m==')'&&n=='#')||
		(m=='^'&&n=='+')||(m=='^'&&n=='-')||(m=='^'&&n=='*')||(m=='^'&&n=='/')||(m=='^'&&n==')')||(m=='^'&&n=='#'))
		return '>';
	else if((m=='('&&n=='+')||(m=='#'&&n=='+')||
		(m=='('&&n=='-')||(m=='#'&&n=='-')||
		(m=='+'&&n=='*')||(m=='-'&&n=='*')||(m=='('&&n=='*')||(m=='#'&&n=='*')||
		(m=='+'&&n=='/')||(m=='-'&&n=='/')||(m=='('&&n=='/')||(m=='#'&&n=='/')||
		(m=='+'&&n=='(')||(m=='-'&&n=='(')||(m=='*'&&n=='(')||(m=='/'&&n=='(')||(m=='('&&n=='(')||(m=='#'&&n=='(')||
		(m=='+'&&n=='^')||(m=='-'&&n=='^')||(m=='*'&&n=='^')||(m=='/'&&n=='^')||(m=='('&&n=='^')||(m=='#'&&n=='^'))return '<';
	else if((m=='('&&n==')')||(m=='#'&&n=='#'))return '=';
	else {printf("表达式形式错误！\n");exit(1);}
}


FElemType fun(float a, float b)                                //乘方
{
	float sum = 1.0 , i;
	for (i = 1 ; i <= b ; i = i+1)
		sum = sum * a;
	return sum;
}


FElemType Operate(float a, char theta, float b)                //运算函数
{
	float 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(1);
		 }
		 c = a / b;
		 break;}
	case '^': c = fun(a,b);
	}
	return c;
}

/*```````````````````````下面三个函数是把字符串转化成实数```````````````````````````*/

FElemType f2(char s[])                     //返回小数部分
{
	int i, j;
	float num = 0.0;
	i = strlen(s);
	for(j = 0 ; s[j] !='\0' ; j++)
		num = 10*num + (s[j]-'0');
	return num/(float)fun(10,i);
}


FElemType f1(char s[])                     //返回整数部分
{
	int j;
	float num = 0.0;
	for (j = 0 ; s[j] !='\0' ; j++)
		num = 10*num + (s[j]-'0');
	return num;
}


FElemType convert(char s[])
{
	int i = 0;
	char s1[8], s2[8];                     //分别存放整数部分和小数部分	 
	while (s[i]!='\0' && s[i]!='.')
	{
		s1[i] = s[i];		 
		i++;
	}
	s1[i] = '\0';                         //s1结束，结尾必须要有'\0'	 
	if (s[i] == '.')
	{
		strcpy(s2,&s[i+1]);               //小数部分复制给s2
		return f1(s1)+f2(s2);             //整数部分加上小数部分
	}
	else
		return f1(s1);
}


			
/*````````````````````````````求值主要子函数````````````````````````*/
FElemType EvaluateExpression(void)
{
	char op[20],c;
	int i=0,mark=0;
	FElemType a,b,m;
	CElemType x,theta;
	FSqStack * OPND;
	CSqStack * OPTR;                           //定义初始变量

	OPTR=InitCStack();                //初始化运算符栈
	PushC(OPTR,'#');                 //运算符栈底押'#'
	OPND=InitFStack();                //初始化操作数栈

	c=getchar();                    //读取输入
	while(c!='#'||GetTopC(OPTR)!='#')
	{
		if(!In(c))
		{
			mark=1;
			op[i++]=c;
			op[i]='\0';
			c=getchar();
		}//if
		else
		{
			if(mark==1)
				{
				m=convert(op);
				OPND=PushF(OPND,m);       Print_FSqStack(OPND);
				mark=0;
				i=0;
				}
			else 
			{                                    printf("当前操作元素为：%c\n",c);
				switch(Precede(GetTopC(OPTR),c))
				{
				case '<':
					OPTR=PushC(OPTR,c);       Print_CSqStack(OPTR);
					c=getchar();
					break;
				case '=':
					x=PopC(OPTR);       Print_CSqStack(OPTR);
					c=getchar();
				    break;
				case '>':
					theta=PopC(OPTR);
					b=PopF(OPND);
					a=PopF(OPND);
					OPND=PushF(OPND,Operate(a,theta,b));       Print_CSqStack(OPTR);
				    break;
				default:return 0;
				}//switch
			}//else
		}//else
	}//while
	if(c=='#'&&i!=0)return convert(op);
	return GetTopF(OPND);
}//EvaluateExpression


int main()
{
	FElemType V;
	CSqStack * Init_CStack(void);
    FSqStack * Init_FStack(void);
    CElemType GetTopC(CSqStack *s);
    FElemType GetTopF(FSqStack *s);
    CSqStack * PushC(CSqStack *s,CElemType e);
    FSqStack * PushF(FSqStack *s,FElemType e);
    CElemType PopC(CSqStack *s);
    FElemType PopF(FSqStack *s);
	void Print_CSqStack(CSqStack * s);
	void Print_FSqStack(FSqStack * s);

	printf("请选择是否进入系统（Y / N）:");
	if(getchar()=='N'){printf("再见! ^_^\n");exit(0);}
loop:	getchar();
	printf("请输入运算表达式：\n");
	V=EvaluateExpression();
	getchar();
	printf("\n");
	printf("表达式值为：%.1f\n",V);
	printf("是否要继续计算表达式（Y / N）:");
	if(getchar()=='Y')goto loop;
	printf("再见! ^_^\n");
	return 0;
}