calculate.cpp

24点游戏,用c++实现

// Caculate.cpp: implementation of the CCalculate class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include <math.h>
#include "Calculate.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

#define MAXPRIORITY 4    //优先级

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

IMPLEMENT_SERIAL(CCalculate, CObject, 0)//序列化
CCalculate::CCalculate()
{
	m_nPos=0;
	m_pRoot=NULL;
	m_strExpression="0";
	m_strWrongMessage="";
	m_bIsValid=FALSE;
}

CCalculate::CCalculate(const CString& strExpression)
{
//	m_strStep=strExpression;
	m_strExpression=strExpression+'\0'+'\0';
	m_strExpression.Replace(" ","");
	m_nPos=0;
	m_pRoot=NULL;
	m_strWrongMessage="";
	m_bIsValid=FALSE;
}

CCalculate::~CCalculate()
{
	FreeTree(m_pRoot);

}

void CCalculate::FreeTree(CNode* nod)
{//释放树节点
	if (nod==NULL) return;
	if (nod->left!=NULL) FreeTree(nod->left);
	if (nod->right!=NULL) FreeTree(nod->right);
	delete nod;
}

//生成一个树
int CCalculate::MakeTree()
{
	//表达式为空
	if (m_strExpression.IsEmpty())
		return 0;

	
	FreeTree(m_pRoot); // Eliberarea memoriei ocupate de arbore
	
	m_pRoot = NULL;
	m_nPos = 0;//m_nPos为结点在树中的编号
	m_pRoot = AddSub();
	if (m_strExpression[m_nPos]!='\0'||!m_strWrongMessage.IsEmpty()) 
	{
		if(m_strWrongMessage.IsEmpty())
			m_strWrongMessage="缺少操作符!";
		FreeTree(m_pRoot);
		m_pRoot = NULL;
	}
	
	if (m_pRoot == NULL)
		return m_nPos;
	else return -1;
}



//构造一个结点
CNode* CCalculate::AddSub()
{//加减
	CNode* nod;
	CNode* left = MultiplyDivide();
	CNode* right;
	if	(left == NULL)
	{
		if(m_strWrongMessage.IsEmpty())
			m_strWrongMessage="缺少操作数";
		return NULL; 
	}
	while ((m_strExpression[m_nPos]=='-') || (m_strExpression[m_nPos]=='+')) 
	{
		
		nod=new CNode;
		nod->left=left;
		nod->operate=m_strExpression[m_nPos];
		nod->prior=4;
		m_nPos++;
		right = MultiplyDivide();
		nod->right=right;
		if	(right == NULL)
		{
			if(m_strWrongMessage.IsEmpty())
				m_strWrongMessage="缺少'+'或'-'的操作数!";
			FreeTree(nod);
			return NULL; 
		}
		left = nod;
	}
	return left;
	
}

//调用了Putere()函数
CNode* CCalculate::MultiplyDivide()
{//乘除
	CNode* nod;
	CNode* left = Putere();
	CNode* right;
	if	(left == NULL) return NULL; 
	while ((m_strExpression[m_nPos]=='*') || (m_strExpression[m_nPos]=='/')) 
	{		
		nod=new CNode;
		nod->left=left;
		nod->operate=m_strExpression[m_nPos];
		nod->prior=3;
		m_nPos++;
		right = Putere();
		nod->right=right;
		if	(right == NULL) 
		{
			if(m_strWrongMessage.IsEmpty())
				m_strWrongMessage="缺少'×'或'÷'的操作数!";
			FreeTree(nod);
			return NULL; 
		}
		left = nod;		
	}
	return left;
}


//求幂的函数 返回的都是一个结点
CNode* CCalculate::Putere()
{//幂
	
	CNode* nod = NULL;
	CNode* arb1 = Factor();
	CNode* arb2;
	if	(arb1 == NULL) return NULL;  // In caz de eroare terminate
	while (m_strExpression[m_nPos]=='^') 
	{
		nod=new CNode;
		nod->left=arb1;
		nod->operate=m_strExpression[m_nPos];
		nod->prior=1;
		m_nPos++;
		arb2 = Factor();
		nod->right=arb2;
		if	(arb2 == NULL) 
		{
			if(m_strWrongMessage.IsEmpty())
				m_strWrongMessage="缺少'^'的操作数!";
			FreeTree(nod);
			return NULL;  // In caz de eroare terminate
		}
		arb1 = nod;
	}
	return arb1;
}


//m_strExpression为表达式的值 
CNode* CCalculate::Factor()
{//括号和绝对值、相反数
	CNode* nod = NULL,*nod2 = NULL,*left = NULL;	//表达式中有可能为''
	while(m_strExpression[m_nPos] == ' ' && m_strExpression[m_nPos] != '\0')
		m_nPos++;

	if (m_strExpression[m_nPos]=='-')//substration
	{
		nod = new CNode;		
		m_nPos++;
//		nod->right = AddSub();//something wrong;
//		nod->right = MultiplyDivide();///
		nod->right=Putere();
		if (nod->right == NULL)
		{
			if(m_strWrongMessage.IsEmpty())
				m_strWrongMessage="缺少'-'(负数)的操作数!";
			FreeTree(nod);
			return NULL;
		}
		else if(nod->right->operate!='@')
		{
			left = new CNode;
			left->left=NULL;
			left->operate='@';
			left->data=-1;
			nod->left=left;
			nod->operate='*';
			nod->prior=0;//将优先级设为0，是因为需要括号的运算。如:---3应变为(-1*(-1*(-3)))
		}
		else
		{

			nod->left=NULL;
			nod->data=-1*nod->right->data;
			delete nod->right;
			nod->right=NULL;
			nod->operate='#';
			nod->prior=0;

		}
		return nod;   
	}
	if (m_strExpression[m_nPos]=='(')//left bracket
	{
		m_nPos++;
		nod = AddSub();		
		if (nod == NULL) return NULL;
		if (m_strExpression[m_nPos]!=')')
		{
			if(m_strWrongMessage.IsEmpty())
				m_strWrongMessage="缺少右括号')'!";
			FreeTree(nod);
			return NULL;
		}
		nod->prior=0;
		m_nPos++;
		return nod;
	}
	else if (m_strExpression[m_nPos]=='|')//abs
	{
		m_nPos++;
		nod2 = AddSub();
		if (nod2 == NULL) return NULL;
		if (m_strExpression[m_nPos]!='|')
		{
			if(m_strWrongMessage.IsEmpty())
				m_strWrongMessage="缺少绝对值操作符'|'!";
			FreeTree(nod);
			return NULL;
		}
		nod = new CNode;
		nod->left=nod2;
		nod->right=NULL;
		nod->operate='|';
		nod->prior=0;
		m_nPos++;
		return nod;
	}
	else return Operand();
	return nod;
}

//operator 
CNode* CCalculate::Operand()
{//操作数
	int nStartPos;//开始位置
	CNode* nod = NULL;
	CNode* result = NULL;
	nStartPos = m_nPos;
	if (m_strExpression[m_nPos]=='\0') result = NULL;
	if (isdigit(m_strExpression[m_nPos]))	// 数字
	{
		while  (isdigit(m_strExpression[m_nPos]) || (m_strExpression[m_nPos]=='.'))	
			m_nPos++;
		nod = new CNode;
		nod->left = NULL; 
		nod->right = NULL;
		nod->operate = '@';
		nod->data = atof(m_strExpression.Mid(nStartPos,m_nPos-nStartPos));//convert the CString to data
		result = nod;
	}
	return result;
}


double CCalculate::Calculate(CNode* node)
{	
	if (node==NULL) 
	{
//		AfxMessageBox(m_strWrongMessage);
		return -1;
	}
	double oper1=0.0,oper2=0.0;
	if(node->left==NULL&&node->right==NULL)
		return node->data;
	else
	{
		oper1=Calculate(node->left);//取左边的数
		oper2=Calculate(node->right);//取右边的数
		
		//calculation
		double result=GetValue(node->operate,oper1,oper2);
//		MakeStep(oper1,oper2,node->operate,result);
		return result;
		
	}
}


//calculation
double CCalculate::GetValue(char operate,double oper1,double oper2)
{
	switch(operate)
	{
		case '*': return oper1*oper2;
		case '/'://特殊的情况
			{
				if (oper2==0) 
				{
//					cout<<"Warning:Denominator cann't be zero"<<endl;
					if(m_strWrongMessage.IsEmpty())
						m_strWrongMessage="除数不能为零!";
//					AfxMessageBox("除数不能为零!",MB_ICONSTOP|MB_OK);
					return 0;
				}
				return oper1/oper2;
			}
		case '+': return oper1+oper2;
		case '-': return oper1-oper2;
		case '|': return fabs(oper1);
		case '^': return pow(oper1,oper2);

	}
	return 0;
}


void CCalculate::Serialize(CArchive& ar)
{
	CObject::Serialize(ar);
	if (ar.IsStoring())
	{
/*		ar << m_m_nPosition;
		ar << (WORD)m_bPen;
		ar.Write(&m_logpen, sizeof(LOGPEN));
		ar << (WORD)m_bBrush;
		ar.Write(&m_logbrush, sizeof(LOGBRUSH));*/
	}
	else
	{
		// get the document back pointer from the archive
/*		m_pDocument = (CMathDoc*)ar.m_pDocument;
		ASSERT_VALID(m_pDocument);
		ASSERT_KINDOF(CMathDoc, m_pDocument);

		WORD wTemp;
		ar >> m_m_nPosition;
		ar >> wTemp; m_bPen = (BOOL)wTemp;
		ar.Read(&m_logpen,sizeof(LOGPEN));
		ar >> wTemp; m_bBrush = (BOOL)wTemp;
		ar.Read(&m_logbrush, sizeof(LOGBRUSH));*/
	}
}


BOOL CCalculate::IsValid(CString* pMessage, int* pPos)
{
	if(MakeTree()!=-1)
	{
		if(pPos!=NULL)
			*pPos=m_nPos;
		if(pMessage!=NULL)
			*pMessage=m_strWrongMessage;
		m_bIsValid=FALSE;
		return FALSE;
	}
	if(pPos!=NULL)
		*pPos=-1;
	if(pMessage!=NULL)
		*pMessage="";
	m_bIsValid=TRUE;
	return TRUE;
}

double CCalculate::GetResult()
{
	if(!m_bIsValid) return 0;
	
	return Calculate(m_pRoot);
}

void CCalculate::ResetExp(const CString &strExp)
{
	m_strExpression=strExp+'\0'+'\0';
}