caluhelp.cpp

将中缀表达式转换为后缀表达式

//
// Module Name: CaluHelp.cpp
//
// Purpose: Implemention of CaluHelp.h
// 
// Programmer: wuwenxi
//
#include "CaluHelp.h"
#include <stdlib.h>
#include <stddef.h>
#include <memory.h>
#include <assert.h>
//#include <stdio.h>

int CompareOperator( char cOp1, char cOp2 );

//-----------------------------
// HelpQueue constructor
//-----------------------------
CCaluHelp::HelpQueue::HelpQueue( )
{
	// Init malloc memory
	m_pMem = new Element[ ALLOC_ONCE ];
	::memset( (void *)m_pMem, 0, (size_t)( ALLOC_ONCE * sizeof(Element) ) );
	m_nAllocCount = ALLOC_ONCE;
	m_pStart = m_pMem;
	m_pEnd = m_pStart + ALLOC_ONCE;
	m_pFree = m_pStart;
}

//-----------------------------
// HelpQueue destructor
//-----------------------------
CCaluHelp::HelpQueue::~HelpQueue( )
{
	if ( m_pMem != NULL )
	{
		delete [] m_pMem;
		m_pMem = NULL;
		m_pStart = NULL;
		m_pEnd = NULL;
		m_pFree = NULL;
	}
}

//----------------------------
// Front
//----------------------------
Element& CCaluHelp::HelpQueue::Front( void )
{
	return *m_pStart++;
}

//----------------------------
// AddToTail
//----------------------------
void CCaluHelp::HelpQueue::AddToTail( const Element & elem )
{
	EnsureCapacity( );
	
	*m_pFree = elem;
	
	++m_pFree;
}

//---------------------------
// Empty
//---------------------------
bool CCaluHelp::HelpQueue::Empty( void ) const
{
	return ( m_pFree == m_pMem ) || ( m_pStart >= m_pFree );
}

//---------------------------
// UsedLength (4 bytes each step)
//---------------------------
int CCaluHelp::HelpQueue::UsedLength( void ) const
{
	return ( int )( m_pFree - m_pStart );
}

//---------------------------
// FreeLength (4 bytes each step)
//---------------------------
int CCaluHelp::HelpQueue::FreeLength( void ) const
{
	return ( int )( m_pEnd - m_pFree );
}

//---------------------------
// EnsureCapacity
//---------------------------
bool CCaluHelp::HelpQueue::EnsureCapacity( void )
{
	if ( m_pFree >= m_pEnd )
	{
		Element * pMemNew = new Element[ m_nAllocCount + ALLOC_ONCE ];
		::memset( (void *)pMemNew, 0, (size_t)( (m_nAllocCount + ALLOC_ONCE) * sizeof( Element ) ) );
		::memcpy( (void *)pMemNew, (void *)m_pStart, (size_t)( (m_pEnd - m_pStart) * sizeof( Element ) ) );
		
		int nOrignalFreeIdx = UsedLength( );
		delete [] m_pMem;
		m_pMem = pMemNew;
		m_nAllocCount += ALLOC_ONCE;
		m_pStart = m_pMem;
		m_pEnd = m_pStart + m_nAllocCount;
		m_pFree = m_pStart + nOrignalFreeIdx;
		
		return true;
	}
	
	return false;
}

//----------------------------
// HelpStack constructor
//----------------------------
CCaluHelp::HelpStack::HelpStack( )
{
	// Empty stack
	m_Top = NULL;
}

//----------------------------
// HelpStack destructor
//----------------------------
CCaluHelp::HelpStack::~HelpStack( )
{
	Clear( );
}

//----------------------------
// Push
//----------------------------
void CCaluHelp::HelpStack::Push( const Element & elem )
{
	HelpStackNode * pNode = new HelpStackNode;
	pNode->value = elem;
	if ( !m_Top )
	{
		m_Top = pNode;
		m_Top->next = NULL;
	}
	else
	{
		pNode->next = m_Top;
		m_Top = pNode;
	}
}

//--------------------------
// Pop
//--------------------------
Element CCaluHelp::HelpStack::Pop( void )
{
	HelpStackNode *pTmp = m_Top;
	m_Top = m_Top->next;
	Element v = pTmp->value;
	delete pTmp;
	return v;
}

//--------------------------
// PopMatch
//--------------------------
void CCaluHelp::HelpStack::PopMatch( const Element & elem, HelpStack& stack )
{
	// if the code exe here, the elem type must be operators,
	// so, we assert it
	assert( elem.type == OPERATOR_TYPE );
	
	HelpStackNode *pTmp = m_Top;
	HelpStackNode *pPrev = pTmp;
	HelpStack      stackTmp;
	while ( pTmp )
	{
		int nRet = CompareOperator( (char)elem.value, (char)pTmp->value.value );
		if ( nRet == 1 )
		{
			if ( pTmp == m_Top )
			{
				if ( pTmp && m_Top->value.value == OP_LEFT_PAR )
					break;
				m_Top = pTmp->next;
				pTmp->next = NULL;
				stackTmp.Push( pTmp->value );
				delete pTmp;
				pTmp = m_Top;
				if ( pTmp && m_Top->value.value == OP_LEFT_PAR )
					break;
			}
			else
			{
				pPrev->next = pTmp->next;
				pTmp->next = NULL;
				stackTmp.Push( pTmp->value );
				delete pTmp;
				pTmp = pPrev;
				pTmp = pTmp->next;
				if ( pTmp && pTmp->value.value == OP_LEFT_PAR )
					break;
			}
		}
		else if ( nRet == 2 )
		{
			// Pop all operators before the first ( character
			assert( pTmp == m_Top );
			
			while ( pTmp && pTmp->value.value != OP_LEFT_PAR )
			{
				stackTmp.Push( pTmp->value );
				pTmp = pTmp->next;
				pPrev->next = NULL;
				delete pPrev;
				pPrev = pTmp;
			}
			
			// pTmp is the OP_LEFT_PAR
			m_Top = pTmp->next;
			pTmp->next = NULL;
			delete pTmp;
			break;
		}
		else
		{
			pPrev = pTmp;
			pTmp = pTmp->next;
		}
	}
	// Reverse the stackTmp elements into parementer stack
	while ( !stackTmp.Empty( ) )
	{
		stack.Push( stackTmp.Pop( ) );
		
	}
}

//-----------------------
// Empty
//-----------------------
bool CCaluHelp::HelpStack::Empty( void ) const
{
	return m_Top == NULL;
}

//----------------------
// ClearStack
//----------------------
void CCaluHelp::HelpStack::ClearStack( void )
{
	Clear( );
}

//----------------------
// Clear
//----------------------
void CCaluHelp::HelpStack::Clear( void )
{
	while ( m_Top != NULL )
	{
		HelpStackNode *pTmp = m_Top;
		m_Top = m_Top->next;
		delete pTmp;
		pTmp = NULL;
	}
}

//----------------------
// CaluExpr
//----------------------
float CCaluHelp::CaluExpr( const char * pcszExpr )
{
	HelpQueue queue;
	ParseExpr( pcszExpr, queue );
	float res = CaluPostfix( queue );
	return res;
}

//----------------------
// ParseExpr
//----------------------
void CCaluHelp::ParseExpr( const char * pcszExpr, HelpQueue& queue )
{
	if ( !::strlen( pcszExpr ) )
		return;
	
	// Copy the pcszExpr to the buffer
	// If not do this, program should falt at assigment to the pointer of pNext!!!
	const int nSize = ::strlen( pcszExpr );
	char buf[ nSize + 1 ];
	::strcpy( buf, pcszExpr );
	buf[ nSize ] = '\0';
	
	char * pStart;
	char * pNext;
	
	HelpStack stack;
	
	pStart = buf;
	pNext = pStart;
	while ( *pNext )
	{
		if ( *pNext != OP_ADD && *pNext != OP_SUB && *pNext != OP_MUL
				&& *pNext != OP_DIV && *pNext != OP_LEFT_PAR
				&& *pNext != OP_RIGHT_PAR
		   )
		{
			if ( *pNext == NEGATIVE )
				*pNext = '-';
			++pNext;
		}
		else
		{
			int nLen = (int)(pNext - pStart);
			//printf("%d \n", nLen);
			char *p = ( char * )malloc( nLen + 1 );
			::strncpy( p, pStart, nLen );
			p[ nLen ] = '\0';
			float f = (float)::atof( p );
			//printf("%f \n", f);
			Element e;
			e.value = f;
			e.type = NUMBER_TYPE;
			queue.AddToTail( e );
			free( p );
			Element o;
			o.value = *pNext;
			o.type = OPERATOR_TYPE;
			HelpStack tmpStack;
			stack.PopMatch( o, tmpStack );
			while ( !tmpStack.Empty( ) )
			{
				queue.AddToTail( tmpStack.Pop( ) );
			}
			stack.Push( o );
			++pNext;
			pStart = pNext;
		}
	}
	// Duplicate code to cope the last float number!
	int nLen = (int)(pNext - pStart);
	//printf("%d \n", nLen);
	char *p = ( char * )malloc( nLen + 1 );
	::strncpy( p, pStart, nLen );
	p[ nLen ] = '\0';
	float f = (float)::atof( p );
	//printf("%f \n", f);
	Element e;
	e.value = f;
	e.type = NUMBER_TYPE;
	queue.AddToTail( e );
	free( p );
	while ( !stack.Empty( ) )
	{
		queue.AddToTail( stack.Pop( ) );
	}
	//assert(!queue.Empty());
}

//----------------------
// CaluPostfix
//----------------------
float CCaluHelp::CaluPostfix( HelpQueue & postfixQueue )
{
	HelpStack caluStack;
	while ( !postfixQueue.Empty( ) )
	{
		Element e = postfixQueue.Front( );
		if ( e.type == NUMBER_TYPE )
		{
			caluStack.Push( e );
		}
		else
		{
			// Pop 2 then do num2 Operator num1 operation
			// Otherwise, the nagitive number could be appear!
			float num1 = caluStack.Pop( ).value;
			float num2 = caluStack.Pop( ).value;
			float frel = 0.0F;
			if ( e.value == OP_ADD )
			{
				frel = num2 + num1;	
			}
			else if ( e.value == OP_SUB )
			{
				frel = num2 - num1;
			}
			else if ( e.value == OP_MUL )
			{
				frel = num2 * num1;
			}
			else if ( e.value == OP_DIV )
			{
				frel = num2 / num1;
			}
			Element e;
			e.value = frel;
			e.type = NUMBER_TYPE;
			caluStack.Push( e );
		}
	}
	// In the result stack, at the end, the only one number is 
	// the calulate ruesult...
	return ( caluStack.Pop( ).value );
}

/*
=========================
CompareOperator
Return value seems FOO!
=========================
*/
int CompareOperator( char cOp1, char cOp2 )
{
	if ( cOp1 == OP_RIGHT_PAR )
		return 2;
	if ( cOp1 == OP_ADD || cOp1 == OP_SUB )
		return 1;
	if ( cOp1 == OP_MUL || cOp1 == OP_DIV )
	{
		if ( cOp2 == OP_MUL || cOp2 == OP_DIV )
			return 1;
	}
	
	return 0;
}