www.pudn.com > MathHead > MathSys.cpp

#include "StdAfx.h" 
#include "MathSys.h" 
 
inline bool IsDigit(wchar_t c) 
{	 
	return (c >= '0' && c <= '9'); 
} 
 
inline bool IsChar(wchar_t c) 
{ 
	if (c >= 'a' && c <= 'z') 
		return true; 
	return (c >= 'A' && c <= 'Z'); 
} 
 
CMathNode::OpType IsOp(wchar_t c) 
{ 
	if (c == '+') 
		return CMathNode::Op_Add; 
	if (c == '-') 
		return CMathNode::Op_Sub; 
	if (c == '*') 
		return CMathNode::Op_Mul; 
	if (c == '/') 
		return CMathNode::Op_Div; 
	if (c == '^') 
		return CMathNode::Op_Exp; 
	if (c == '(') 
		return CMathNode::Op_ParOpen; 
	if (c == ')') 
		return CMathNode::Op_ParClose; 
 
	return (CMathNode::Op_Null); 
} 
 
 
std::ostream & operator<<(std::ostream & lhs, CMathNode & rhs); 
 
 
 
// Parses a mathematical expression. 
int CMathSys::ParseString(wchar_t * wszInput, CMathNode** ppTree) 
{ 
	if (!wszInput || !ppTree) 
		return MATHSYS__NULL_INPUT; 
 
	list * pList = NULL; 
	int nRet; 
 
	nRet = BuildList(wszInput, &pList); 
 
	if (nRet != MATHSYS__SUCCESS) 
		return nRet; 
 
	nRet = MakeTree(pList, ppTree); 
 
	delete pList; 
     
	return nRet; 
} 
 
// Builds a list of CMathNode's from a string 
int CMathSys::BuildList(wchar_t * wszInput, list** ppList) 
{ 
	wchar_t		wBuffer[MATHSYS__MAX_TOKEN_BUFFER]; 
	wchar_t *	pNext = wszInput - 1; 
	CMathNode * pNodeNext = NULL; 
 
	*ppList = new list; 
 
	CMathNode::OpType op; 
 
	while(true) 
	{ 
		pNext++; 
		wchar_t cNext = *pNext; 
		if (cNext == 0) 
			break; 
		if (cNext == ' ') 
			continue; 
		else if (IsDigit(cNext) || cNext == '.') 
		{ 
			int i = 0; 
			bool bFoundDecimal = false;// = (cNext == '.'); 
			while(true) 
			{ 
				if (!IsDigit(*pNext)) 
					if (!(*pNext == '.')) 
						break; 
					else 
						if (bFoundDecimal) 
							return MATHSYS__BAD_INPUT;	// A second decimal point was found 
						else 
							bFoundDecimal = true; 
 
				wBuffer[i++] = *(pNext++); 
			} 
			wBuffer[i] = 0;	// Null char 
			--pNext; 
			pNodeNext = new CMathNode; 
			if (!bFoundDecimal) 
				pNodeNext->MakeExact(_wtoi64(wBuffer)); 
			else 
				pNodeNext->MakeApprox(_wtof(wBuffer)); 
			(*ppList)->push_back(pNodeNext); 
 
		} 
		else if (op = IsOp(cNext)) 
		{ 
			int i = 0; 
			while (true) 
			{ 
				if (!IsChar(*pNext)) 
					break; 
				wBuffer[i++] = *(pNext++); 
			} 
			wBuffer[i] = 0;	// Null char 
 
			pNodeNext = new CMathNode; 
			pNodeNext->MakeOp(op); 
			(*ppList)->push_back(pNodeNext); 
		} 
		else if (IsChar(cNext)) 
		{ 
			int i = 0; 
			pNodeNext = new CMathNode; 
			pNodeNext->MakeVar(cNext); 
			(*ppList)->push_back(pNodeNext); 
		} 
		else 
		{ 
			// Bad input 
			FreeNodeList(*ppList); 
			return MATHSYS__BAD_INPUT; 
		} 
	} 
 
	if ((*ppList)->size() == 0) 
		return MATHSYS__BAD_INPUT; 
 
	return MATHSYS__SUCCESS; 
} 
 
 
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 
void GetNodeDescription(CMathNode* pTree, WCHAR * wBuffer); 
 
 
int CMathSys::MakeTree(list* pList, CMathNode ** ppTree) 
{ 
	/******************* 
 
	Order of Operations 
	1. Parentheses	- Sort inner elements 
	2. Exponent 
	3. Multiplication, Division 
	4. Addition, Subtraction 
 
	*******************/ 
 
	CMathNode * pNode = NULL; 
	iterator iNext = pList->begin(); 
	iterator iStart, iEnd, iArg; 
 
	int nParLevel = 0; 
 
	if (pList->size() == 0) 
		return MATHSYS__BAD_INPUT; 
 
	list lSub; 
 
	// 1. Parentheses 
	while(iNext != pList->end()) 
	{ 
/* 
		Search for the first open paranthesis, mark it, and set 
		nParLevel to 1. When another is found, nParLevel++. 
		When a closed parenthesis is found, nParLevel--, until 
		nParLevel == 0. Splice on [ iStart, iEnd ) and MakeTree 
		on the sublist. 
*/ 
 
		pNode = *iNext; 
		if (pNode->m_Type == CMathNode::Node_Op) 
		{	 
			if (pNode->m_Op == CMathNode::Op_ParOpen) 
			{ 
				if (nParLevel) 
					nParLevel++;	// Increase level 
				else 
				{ 
					iStart = iNext; 
					nParLevel = 1; 
				} 
			} 
			else if (pNode->m_Op == CMathNode::Op_ParClose) 
			{ 
				if (--nParLevel == 0) 
				{ 
					iterator iRemove = iStart;		// iRemove = '(' 
					iEnd = iNext; 
					iNext++;						// Move iNext past ')' so it is still valid after this iteration 
					iStart++;						// Move iStart past '(' 
					lSub.splice(lSub.begin(), *pList, iStart, iEnd); 
					 
					CMathNode * pNew = NULL; 
					if (MakeTree(&lSub, &pNew) != MATHSYS__SUCCESS) 
					{ 
						FreeNodeList(&lSub); 
						return MATHSYS__FAILURE; 
					} 
 
					delete (*iRemove); 
					iRemove = pList->erase(iRemove); 
					delete (*iRemove); 
					iArg = pList->erase(iRemove); 
 
					pList->insert(iArg, pNew); 
 
					nParLevel = 0; 
					continue; 
				} 
			} 
		} 
 
		iNext++; 
	} 
 
	// 2. Exponents 
	iNext = pList->begin(); 
	while(iNext != pList->end()) 
	{ 
		pNode = *iNext; 
		if (pNode->m_Type == CMathNode::Node_Op) 
		{	 
			if (pNode->m_Op == CMathNode::Op_Exp) 
			{ 
				if (pNode->m_pSubArray[0].m_Type != CMathNode::Node_Null) 
				{ 
					// This already has subs (it was in parentheses) 
					iNext++; 
					continue; 
				} 
 
				iArg = iNext; 
				(*(--iArg))->MoveTo(&pNode->m_pSubArray[0]);	// Move previous to the first sub 
				delete (*iArg); 
				pList->erase(iArg); 
 
				iArg = iNext; 
				(*(++iArg))->MoveTo(&pNode->m_pSubArray[1]);	// Move next to the first sub 
				delete (*iArg); 
				pList->erase(iArg); 
			} 
		} 
 
		iNext++; 
	} 
 
	// 3. Multiplication / Division 
	iNext = pList->begin(); 
	while(iNext != pList->end()) 
	{ 
		pNode = *iNext; 
		if (pNode->m_Type == CMathNode::Node_Op) 
		{	 
			if (pNode->m_Op == CMathNode::Op_Mul || pNode->m_Op == CMathNode::Op_Div) 
			{	 
				if (pNode->m_pSubArray[0].m_Type != CMathNode::Node_Null) 
				{ 
					// This already has subs (it was in parentheses) 
					iNext++; 
					continue; 
				} 
				 
				iArg = iNext; 
				(*(--iArg))->MoveTo(&pNode->m_pSubArray[0]);	// Move previous to the first sub 
				delete (*iArg); 
				pList->erase(iArg); 
 
				iArg = iNext; 
				(*(++iArg))->MoveTo(&pNode->m_pSubArray[1]);	// Move next to the first sub 
				delete (*iArg); 
				pList->erase(iArg); 
			} 
		} 
 
		iNext++; 
	} 
 
	// 4. Addition / Subtraction 
	iNext = pList->begin(); 
	while(iNext != pList->end()) 
	{ 
		pNode = *iNext; 
		if (pNode->m_Type == CMathNode::Node_Op) 
		{	 
			if (pNode->m_Op == CMathNode::Op_Add || pNode->m_Op == CMathNode::Op_Sub) 
			{ 
				if (pNode->m_pSubArray[0].m_Type != CMathNode::Node_Null) 
				{ 
					// This already has subs (it was in parentheses) 
					iNext++; 
					continue; 
				} 
 
				iArg = iNext; 
				(*(--iArg))->MoveTo(&pNode->m_pSubArray[0]);	// Move previous to the first sub 
				delete (*iArg); 
				pList->erase(iArg); 
 
				iArg = iNext; 
				(*(++iArg))->MoveTo(&pNode->m_pSubArray[1]);	// Move next to the first sub 
				delete (*iArg); 
				pList->erase(iArg); 
			} 
		} 
 
		iNext++; 
	} 
 
	// Pointer now "owns" the tree in memory 
	*ppTree = pList->front(); 
 
	// Don't bother freeing the tree 
	pList->empty(); 
 
	return MATHSYS__SUCCESS; 
} 
 
 
 
void CMathSys::FreeNodeList(list* pList) 
{ 
	using std::list::iterator; 
 
	for (iterator i = pList->begin(); i != pList->end(); i++) 
		delete (*i);	// CMathNode* 
}