表达式求值.cpp

属于利用C++开发的数据结构代码

#include"iostream.h"
#include"stdlib.h"
#include"stdio.h"
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 10
#define ElemType char
#define NULL 0 
typedef struct{
	ElemType *base;
	ElemType *top;
	int stacksize;
}SqStack;

typedef struct{
	float *base;
	float *top;
	int stacksize;
}FloatStack;

int InitStack(SqStack &S)
{
	//构造一个空的字符栈S
	S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
	if(!S.base) exit(0);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return 1;
}

int InitFStack(FloatStack &S)
{
	//构造一个空的数字栈S
	S.base=(float *)malloc(STACK_INIT_SIZE*sizeof(float));
	if(!S.base) exit(0);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return 1;
}

int InitOP(SqStack &S)
{
	//构造一个符号栈S
	char OP[]={'+','-','*','/','(',')','='};
	int i;
	S.base=(ElemType *)malloc(10*sizeof(ElemType));
	if(!S.base) exit(0);
	S.top=S.base;
	S.stacksize=10;
	for(i=0;i<7;i++)
		*S.top++=OP[i];
	return 1;
}

ElemType GetTop(SqStack S)
{
	//若栈不空，则返回S的栈顶元素；否则返回e
	ElemType e;
	if(S.top==S.base) return 'e';
	e=*(S.top-1);
	return e;
}

float GetFTop(FloatStack S)
{
	//若栈不空，则返回S的栈顶元素；否则返回-1
	float e;
	if(S.top==S.base) return -1;
	e=*(S.top-1);
	return e;
}

int Push(SqStack &S,ElemType e)
{
	//插入元素e为新的栈顶元素
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
		if(!S.base) exit(0);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
	return 1;
}

int PushF(FloatStack &S,float e)
{
	//插入元素e为新的栈顶元素
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(float *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
		if(!S.base) exit(0);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
	return 1;
}

int Pop(SqStack &S,ElemType &e)
{
	//若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0
	if(S.top==S.base) return 0;
	e=*--S.top;
	return 1;
}

int PopF(FloatStack &S,float &e)
{
	//若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0
	if(S.top==S.base) return 0;
	e=*--S.top;
	return 1;
}

int In(ElemType c,SqStack S)
{
	//判断元素c是否在运算符集合S中，若在，返回1；否则，返回0。
	ElemType *p;
	for(p=S.base;p!=S.top;p++)
		if(c==*p) return 1;
	return 0;
}

int Times(int a,int b)
{
	int r=1;
	for(int i=0;i<b;i++)
		r*=a;
	return r;
}

char Precede(char a,char b)
{
	//判定运算符a和b之间的优先关系
	switch(a)
	{
	case '+':
		switch(b)
		{
		case '+':
			return('>');
		case '-':
			return('>');
		case '*':
			return('<');
		case '/':
			return('<');
		case '(':
			return('<');
		case ')':
			return('>');
		case '=':
			return('>');
		}
	case '-':
		switch(b)
		{
		case '+':
			return('>');
		case '-':
			return('>');
		case '*':
			return('<');
		case '/':
			return('<');
		case '(':
			return('<');
		case ')':
			return('>');
		case '=':
			return('>');
		}
	case '*':
		switch(b)
		{
		case '+':
			return('>');
		case '-':
			return('>');
		case '*':
			return('>');
		case '/':
			return('>');
		case '(':
			return('<');
		case ')':
			return('>');
		case '=':
			return('>');
		}
	case '/':
		switch(b)
		{
		case '+':
			return('>');
		case '-':
			return('>');
		case '*':
			return('>');
		case '/':
			return('>');
		case '(':
			return('<');
		case ')':
			return('>');
		case '=':
			return('>');
		}
	case '(':
		switch(b)
		{
		case '+':
			return('<');
		case '-':
			return('<');
		case '*':
			return('<');
		case '/':
			return('<');
		case '(':
			return('<');
		case ')':
			return('=');
		}
	case ')':
		switch(b)
		{
		case '+':
			return('>');
		case '-':
			return('>');
		case '*':
			return('>');
		case '/':
			return('>');
		case ')':
			return('>');
		case '=':
			return('>');
		}
	case '=':
		switch(b)
		{
		case '+':
			return('<');
		case '-':
			return('<');
		case '*':
			return('<');
		case '/':
			return('<');
		case '(':
			return('<');
		case '=':
			return('=');
		}
	default:
		return 'E';
	}
}

float Operate(float a,char theta,float b)
{
	//返回运算结果
	switch(theta)
	{
	case '+':
		return a+b;
	case '-':
		return a-b;
	case '*':
		return a*b;
	default:
		return a/b;
	}
}


//表达式求值
float EvaluateExpression()
{
	//算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，
	//OP为运算符集合。
	char c,x,theta;
	float a,b,D[10]={0};
	int I[10]={0},i=0,j=0,flag=0,trig=0;//flag=0时,存入整数部分栈中;flag=1时,存入小数部分栈中;
	SqStack OPTR,OP;                    //trig=0时,把读入的数据存入栈中;trig=0时,不读入数据
	FloatStack OPND; 
	InitOP(OP);
	InitStack(OPTR);	Push(OPTR,'=');
	InitFStack(OPND);
	c=getchar();
	while(c!='='||GetTop(OPTR)!='=')
	{
		if(!In(c,OP))
		{
			if(flag==0)
			{
				I[i]=int(c)-48;
				i++;
				c=getchar();
			}
			if(c=='.')
			{
				flag=1;
				c=getchar();
			}
			if(flag==1)
			{
				D[j]=float(c)-48;
				j++;
				c=getchar();
			}
			
		}
		else
		{
			if(trig==0)
			{
				float f=0;
				int k;
				for(k=0;I[k]!=0;k++,i--)
				{
					f+=I[k]*Times(10,i-1);
					I[k]=0;
				}	
				for(k=0;D[k]!=0;k++,j--)
				{
					f+=D[k]/Times(10,k+1);
					D[k]=0;
				}
				if(c!='(')
					if(c!=')')
						PushF(OPND,f);
					else if(GetTop(OPTR)!='(')
						PushF(OPND,f);
				flag=0;
			}
			trig=0;
			switch(Precede(GetTop(OPTR),c))
			{
			case '<':	//栈顶元素优先权低
				Push(OPTR,c);
				c=getchar();
				if(In(c,OP))
					trig=1;
				break;
			case '=':	//脱括号并接收下一个字符
				Pop(OPTR,x);
				c=getchar();
				if(In(c,OP))
					trig=1;
				break;
			case '>':   //退栈并将运算结果入栈
				Pop(OPTR,theta);
				PopF(OPND,b);
				PopF(OPND,a);
				PushF(OPND,Operate(a,theta,b));
				trig=1;
				break;
			}
		}
	}
	return GetFTop(OPND);
}

void main()
{
	cout<<"请输入所求表达式:"<<endl;
	cout<<EvaluateExpression()<<endl;
}