数据结构实现－堆栈－堆栈应用－中序 到 后序的转换和计算[anank].cpp

包含了数据结构实现堆栈的方法。 主要有链表实现和数组实现以及堆栈的应用。

/*****************************************************************************************************
** Program Name : Transform Mid-Order to Pos-Order
** Author       : Lu Jian Hua
** Time         : 2007-5-24
*****************************************************************************************************/

#include <iostream>
using namespace std ;

class Stack_Int									// class of Stack(elements in it are integers)
{
public:
	Stack_Int(int max_size) ;					// constructor
	int  GetTopValue() const ;					// get the top value of stack
	void Push(int value) ;						// push
	int  Pop() ;								// pop
	bool IsEmpty() ;							// is empty ?
	bool IsFull() ;								// is full ?
	enum { MAX_SIZE = 10 } ;
	int top ;
	int element[MAX_SIZE] ;
} ;

Stack_Int::Stack_Int(int max_size) : top(-1) {}

int Stack_Int::GetTopValue() const
{
	if (top < 0)
	{
		cout << "The stack is empty!   " ;
		return 0 ;
	}

	return element[top] ;
}

void Stack_Int::Push(int value)					
{
	if (top >= MAX_SIZE-1)
	{
		cout << "The stack is full!    " << endl << endl ;
		return ;
	}

	top++ ;									// 1> move the top
	element[top] = value ;					// 2> infill the element
}

int Stack_Int::Pop()							
{
	if (top < 0)
	{
		cout << "The stack is empty!    " ;
		return 0 ;
	}

	int temp = element[top] ;				// 1> get value
	top-- ;									// 2> move top
	return temp ;
}

bool Stack_Int::IsEmpty()						
{
	return ( top < 0 ) ;
}

bool Stack_Int::IsFull()
{
	return ( top >= MAX_SIZE-1 ) ;			
}

class Stack									// class of Stack(elements in it are chars)
{
public:
	Stack(int max_size) ;					// constructor
	char  GetTopValue() const ;				// get the top value of stack
	void Push(char value) ;					// push
	char  Pop() ;							// pop
	bool IsEmpty() ;						// is empty ?
	bool IsFull() ;							// is full ?
	enum { MAX_SIZE = 10 } ;
	int top ;
	char element[MAX_SIZE] ;
} ;

Stack::Stack(int max_size) : top(-1) {}

char Stack::GetTopValue() const
{
	if (top < 0)
	{
		cout << "The stack is empty!   " ;
		return 0 ;
	}

	return element[top] ;
}

void Stack::Push(char value)					
{
	if (top >= MAX_SIZE-1)
	{
		cout << "The stack is full!    " << endl << endl ;
		return ;
	}

	top++ ;									// 1> move the top
	element[top] = value ;					// 2> infill the element
}

char Stack::Pop()							
{
	if (top < 0)
	{
		cout << "The stack is empty!    " ;
		return 0 ;
	}

	char temp = element[top] ;				// 1> get value
	top-- ;									// 2> move the top
	return temp ;
}

bool Stack::IsEmpty()						
{
	return ( top < 0 ) ;
}

bool Stack::IsFull()
{
	return ( top >= MAX_SIZE-1 ) ;			
}

/*----------------------------------------------------------------------------------------------
  Function Name : Prio_Outer
  Parameters    :
					char c  (the operator in form of char)
  Value Returned:	int		(the privous of a certain opertor)
  Details       : obtain a previous of a certain opertor
-----------------------------------------------------------------------------------------------*/
int Prio_Outer(char c)
{
	int prio = 0 ;

	switch (c)
	{
	case '(':	prio=3;		break ;
	case ')':	prio=0;		break ;
	case '+':	prio=1;		break ;
	case '-':	prio=1;		break ;
	case '*':	prio=2;		break ;
	case '/':	prio=2;		break ;
	default:	prio=-1;	break ;
	}

	return prio ;
}


/*----------------------------------------------------------------------------------------------
  Function Name : Prio_Outer
  Parameters    :
					char c  (the operator in form of char)
  Value Returned:	int		(the privous of a certain opertor)
  Details       : obtain a previous of a certain opertor
-----------------------------------------------------------------------------------------------*/
int Prio_Inner(char c)
{
	int prio = 0 ;

	switch (c)
	{
	case '(':	prio=0;		break ;
	case '+':	prio=1;		break ;
	case '-':	prio=1;		break ;
	case '*':	prio=2;		break ;
	case '/':	prio=2;		break ;
	case '#':	prio=-1;	break ;
	default:	prio=-1;	break ;
	}

	return prio ;
}

/*----------------------------------------------------------------------------------------------
  Function Name : Convertor
  Parameters    :
				char *ptr	: the string to be transformed
				Stack* stk	: the stack to be used
				char *dest	: to store the string have been transformed
				int dest_sie: the length of the destination 
  Value Returned: void
  Details       : transform the string expression
------------------------------------------------------------------------------------------------*/
void Convertor(char *ptr, Stack* stk, char *dest, int dest_size)	// Inversor 
{
	int i = 0 ;
	int LENGTH = strlen(ptr) ;
	int j = 0 ;

	for (i=0; i<dest_size; i++)			// initialize all characters of destination '\0'
		*(dest+i) = '\0' ;

	for (i=0; i<LENGTH; i++)
	{
		char c = *(ptr+i) ;

		switch (c) 
		{
		case '(':						// if '(', push directly
			stk->Push(c) ;	
			break ;
		/*-------------------------------------------------------------*/
		case ')':						// if ')', pop until '(' appear
			while (true)
			{
				if (stk->top < 0)		// if stack is empty, stop working
					break ;

				char c = stk->Pop() ;
				
				if (c == '(')			// if operator poped is '(', stop
					break ;
				else					// output it
				{
					cout << c ;
					*(dest+j++) = c ;
				}
			}
			break ;
		/*-------------------------------------------------------------*/
		case '+':								// +, -, *, /
		case '-':
		case '*':
		case '/':
			while (true)
			{
				if (stk->top < 0)
					break ;

				char top_char = stk->GetTopValue() ;

				if ( Prio_Outer(c) <= Prio_Inner(top_char) )	// if previous[OUTTER] <= previous[INNER]
				{
					char temp = stk->Pop() ;
					cout << temp ;
					*(dest+j++) = temp ;
				}
				else
				{
					stk->Push(c) ;
					break ;
				}
			} //end while
			break ;
		/*-------------------------------------------------------------*/
		default:								// if it's a character or a number
			cout << c ;
			*(dest+j++) = c ;
			break ;
		
		}// end switch
	}// end for

	while (true)
	{
		if ( stk->IsEmpty() || stk->GetTopValue() == '#')
			break ;

		char temp = stk->Pop() ;
		cout << temp ;
		*(dest+j++) = temp ;
	}
}

/*----------------------------------------------------------------------------------------------
  Function Name : GetIntValue
  Parameters    :
					char c
  Value Returned: int
  Details       : transform a character to its corresponding digital
------------------------------------------------------------------------------------------------*/

int GetIntValue(char c)
{
	int value = 0 ;

	switch (c)
	{
		case '1':	value=1;	break;
		case '2':	value=2;	break;
		case '3':	value=3;	break;
		case '4':	value=4;	break;
		case '5':	value=5;	break;
		case '6':	value=6;	break;
		case '7':	value=7;	break;
		case '8':	value=8;	break;
		case '9':	value=9;	break;
		default:	value=0;	break;
	}

	return value ;
}
/*----------------------------------------------------------------------------------------------
  Function Name : Compute
  Parameter     :
				  char *ptr		(the expression to be computed)
				  Stack *stk	(the stack will be used, integers will be stored in it)
  Value Returned: int
  Details       : compute the Pos-Order expression
------------------------------------------------------------------------------------------------*/

int Compute(const char *ptr, Stack_Int *stk)
{
	while (true)						// clean the stack
	{
		if ( stk->IsEmpty() )
			break ;

		stk->Pop() ;
	}

	int i = 0 ;
	int LENGTH = strlen(ptr) ;
	int op1 = 0 ;
	int op2 = 0 ;

	for (i=0; i<LENGTH; i++)
	{
		char c = *(ptr+i) ;

		switch (c)
		{
		case '+':	
			op1 = stk->Pop() ;
			op2 = stk->Pop() ;	
			stk->Push(op2+op1) ;
			break ;
		case '-':	
			op1 = stk->Pop() ;
			op2 = stk->Pop() ;
			stk->Push(op2-op1) ;
			break ;
		case '*':
			op1 = stk->Pop() ;
			op2 = stk->Pop() ;
			stk->Push(op2*op1) ;
			break ;
		case '/':
			op1 = stk->Pop() ;
			op2 = stk->Pop() ;
			stk->Push(op2/op1) ;
			break ;
		default:
			stk->Push( GetIntValue(c) ) ;
			break ;
		}
	} // end for

	return ( stk->Pop() ) ;
}


int main()
{
	Stack stk = Stack(20) ;
	stk.Push('#') ;
	char str[100] ;
	char dest[100] ;
	Stack_Int stk_int = Stack_Int(20) ;

	while (true)
	{
		cout << "--------------------------------------------" << endl ;
		cout << "Please enter the string : " ;
		cin  >> str ;
		cout << "\nBefore Convert :  " << str << endl << endl ;
		cout << "After  Convert :  " ;
		Convertor(str, &stk, dest, 100) ;
		cout << endl << endl ;
		cout << "Computing..." << endl << endl 
			 << "dest: " << dest << endl << endl
			 << "Result : " << Compute(dest, &stk_int) << endl << endl ;
	}
	
	return 0 ;
}


/********************************************************************************
*
* Notice : This Program Can Be Launched In VC6.0 Environment
*
********************************************************************************/