表达式求值.cpp

按照清华大学的那本数据结构的表达式求值改进

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

//状态码
#define TRUE    1
#define FALSE   0
#define OK      1
#define ERROR   0
#define NULL    0
#define INFEASIBLE -1
#define OVERFLOW   -2
typedef int Status;

typedef char OPTRElemType;  //运算符栈的元素类型
typedef double OPNDElemType; //操作数栈的元素类型

#include"OPNDStack.h"
#include"OPTRStack.h"

#define MaxWordNum 100				//数据的最大位数
#define MaxWordLength 100			//输入的最多字符数

//全局变量
char OPTROPND[MaxWordNum][MaxWordLength];  //存放操作数和运算符号的二维数组
int CurrentNum;  //已经检测的操作数和运算符号个数
char* Current;  //当前检测的字符
char* Pre;  //上一个检测的字符
char Expression[100]; //辅助空间

#include"复件 sortExpression.h"  //检查输入的表达式子是否合法,并且把输入的表达式
                            //分成3种类型:运算符,浮点数,整数.

char *OP="+-*/()#";             //OP为运算符集合.
char relation[7][7]={           //算符间的优先关系矩阵
	{'>','>','<','<','<','>','>'},
	{'>','>','<','<','<','>','>'},
	{'>','>','>','>','<','>','>'},
	{'>','>','>','>','<','>','>'},
	{'<','<','<','<','<','=',' '},
	{'>','>','>','>',' ','>','>'},
	{'<','<','<','<','<',' ','='}};
int Find(char a)
{//查询运算符a在运算符集合OP中的序号.
 int i;
 for (int j=0;j<=6;j++) {if( OP[j]==a) i=j;}
 return i;
}
Status In(char a,char *op)
{//判别a是否属于运算符集合op.
 if(a=='\0') return FALSE;
 for (char *p=op;(p<=op+strlen(op))&&(*p!=a);p++);
 if (p<=op+strlen(op)) return TRUE;
 else return FALSE;
}
OPTRElemType Precede(char a,char b)
{//求运算符a与b的优先级.
 int A,B;
 A=Find(a);
 B=Find(b);
 return relation[A][B];
}
double Operate(double a,OPTRElemType theta,double b)
{//计算a theta b 的值
 switch(theta)
  {case'+': return a+b;
   case'-': return a-b;
   case'*': return a*b;
   case'/': return a/b;
   default: exit(OVERFLOW); }
}
char* GetWord(int index)
{//返回第index个操作数的指针
	if(index>=CurrentNum) //超出范围
		return NULL;
	else
		return OPTROPND[index];
}
Status IsAllDouble()
{//判断表达式运算是否为浮点数运算
	for(int i=0;i<CurrentNum;i++)
	{//查找操作数中是否存在'.'和'/'若有则返回真
		for(int j=0;j<MaxWordLength;j++)
		if(OPTROPND[i][j]=='.'||!strcmp(OPTROPND[i],"/"))
			return TRUE;
	}
	return FALSE;
}
//浮点数运算
double EvaluateExpressiondouble()
{//算术表达式求值的算符优先算法.  设OPTR和OPND分别为运算符栈和运算数栈.
    OPTRSqStack OPTR; //运算符栈
	OPNDSqStack OPND; //操作数栈
	OPTRElemType x;
	InitOPTRStack(OPTR);  Push(OPTR,'#');  
	InitOPNDStack(OPND); 
	int WordIndex = 0; //计数器
	while(strcmp(GetWord(WordIndex),"#")!=0||GetTop(OPTR)!='#')
	{
		if(!In(GetWord(WordIndex)[0],OP))
		{
			double value=atof((GetWord(WordIndex)));
			Push(OPND,value);  WordIndex++;
		}
		else
		switch(Precede(GetTop(OPTR),GetWord(WordIndex)[0]))
		{
		case'<':  //栈顶元素优先权低
			Push(OPTR,GetWord(WordIndex)[0]); WordIndex++; break;
		case'=':  //脱括号并接收下一个字符
			Pop(OPTR,x); WordIndex++;  break;
		case'>':  //退栈并将运算结果入栈
			double a,b; char theta;
			     Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a);
			     Push(OPND,Operate(a,theta,b)); break;
		}
	}
	return GetTop(OPND);
}
//整数运算
int EvaluateExpressionint()
{
	OPTRSqStack OPTR; //运算符栈
	OPNDSqStack OPND; //操作数栈
	OPTRElemType x;  
	InitOPTRStack(OPTR);  Push(OPTR,'#');  
	InitOPNDStack(OPND); 
	int WordIndex = 0; //计数器
	while(strcmp(GetWord(WordIndex),"#")!=0||GetTop(OPTR)!='#')
	{
		if(!In(GetWord(WordIndex)[0],OP)) 
		{
			int value=atoi((GetWord(WordIndex)));
			Push(OPND,value);  WordIndex++;
		}
		else
		switch(Precede(GetTop(OPTR),GetWord(WordIndex)[0]))
		{
		case'<':  //栈顶元素优先权低
			Push(OPTR,GetWord(WordIndex)[0]); WordIndex++; break;
		case'=':  //脱括号并接收下一个字符 
			Pop(OPTR,x); WordIndex++;  break;
		case'>':  //退栈并将运算结果入栈
			double a,b; OPTRElemType theta;
			     Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a);
			     Push(OPND,Operate(a,theta,b)); break;
		}
	}
	return (int)(GetTop(OPND));
}
void main()
{
	char *chExpression;
	chExpression=(char*)malloc(MaxWordNum*sizeof(char));
	cout<<"请输入表达式子(以'#'结束):";
    cin>>chExpression;
	while(!sortExpression(chExpression))
	{
		cout<<"输入的表达式有错误!请重新输入!"<<endl;
		cout<<"请输入表达式子(以'#'结束):";
	    cin>>chExpression;
		sortExpression(chExpression);
	}
	if(IsAllDouble())  //浮点数运算
	{
		cout<<"结果为:"<<EvaluateExpressiondouble()<<endl;
	}
	else 
	{  //整数计算
		cout<<"结果为:"<<EvaluateExpressionint()<<endl;
	}
}