main.cpp

基本算法处理：表达式分析

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

typedef struct stackItemtag
{
	double item;
	stackItemtag *next;
}StackItem;

typedef StackItem *Stack;

double soluteExpression( char * );
bool push( Stack &, double );
bool pop( Stack &, double& );
int comp( char, char );//1:higher,0:equal,-1:lower
double cal( double, double, char ); 
void reportError();

void main()
{
	char s[ 100 ];
	int i;
start:
	cout << "Please input the exprission you want to solute( maximum length 97 chars ):" << endl;
	cin.getline( s + 1, 98 );
	s[ 0 ] = '(';
	i = strlen( s );
	s[ i ] = ')';
	s[ i + 1 ] = '\0';
	cout << "The solution is: " << soluteExpression( s ) << endl;
	cout << endl << "Press 1 to solute again...." << endl;
	cin >> i;
	if( i == 1 )
	{
		cin.ignore( 0x7ffff, '\n' );
		goto start;
	}
}

bool push( Stack &s, double i )
{
	StackItem *temp;
	if( !( temp = new StackItem ) )
		return false;
	else
	{
		temp->item = i;
		temp->next = s;
		s = temp;
	}
	return true;
}

bool pop( Stack &s, double &a )
{
	if( s == NULL )
		return false;
	Stack temp = s->next;
	a = s->item;
	delete s;
	s = temp;
	return true;
}
	
int comp( char a, char b )
{
	//compare priority
	if( a == '*' || a == '/' )
	{
		if( b == '*' || b == '/' )
			return 0;
		else
			return 1;
	}
	else
	{
		if( b == '+' || b == '-' )
			return 0;
		else
			return -1;
	}
}

double cal( double a, double b, char c )
{
	if( c == '+' )
		return a + b;
	if( c == '-' )
		return a - b;
	if( c == '*' )
		return a * b;
	if( c == '/' )
		return a / b;
}

void reportError()
{
	cout << endl << " * * * Input error! * * * " << endl;
	exit( 0 );
}

double soluteExpression( char *s )
{
	//////////////////////////////////////////////////////////////////////////
	//Program by tony@zzxy
	//Instruction:
	//The input string s must be as such format:
	//"(......)" + '\0'
	//space ' ' is automatically ignored.
	//////////////////////////////////////////////////////////////////////////
	
	double a, b;//operater num
	double oper, tag = 0, brace = 0, digitAfterDot = 0;//tag = 1:solving numbers
	double temp = 0, tempAfterDot;//store temporary data
	Stack op = NULL, data = NULL;
	for( int i = 0; s[ i ]; i++ )
	{
		if( s[ i ] == ' ' )
			continue;
		if( ( s[ i ] >= '0' && s[ i ] <= '9' ) || s[ i ] == '.' )
		{
			if( s[ i ] == '.' )
			{
				if( digitAfterDot == 0 )
					digitAfterDot = 1;
				else
				{
					reportError();
				}
				continue;
			}

			if( digitAfterDot == 0 )
				temp = temp * 10 + ( int )( s[ i ] - 0x30 );
			else
			{
				tempAfterDot = ( int )s[ i ] - 0x30;
				for( int j = 0; j <= digitAfterDot - 1; j++ )
				{
					tempAfterDot /= 10;
				}
				temp +=tempAfterDot;
				digitAfterDot++;
			}
			tag = 1;
		}
		else if( s[ i ] != '+' && s[ i ] != '-' && s[ i ] != '*' && s[ i ] != '/' && s[ i ] != '('
			&& s[ i ] != ')' )
		{
			reportError();
		}
		else
		{
			if( tag == 1 )
			{
				push( data, temp );
				tag = 0;
				digitAfterDot = 0;				
				temp = 0;
			}
			if( !op || s[ i ] == '(' )
				push( op, s[ i ] );
			else
			{
				if( s[ i ] == ')' )
				{
					while( op->item != '(' )
					{
						if( !pop( data, a ) || !pop( data, b ) )
						{
							reportError();
						}
						pop( op, oper );
						push( data, cal( b, a, oper ) );
					}
					pop( op, oper );
				}
				else if( op->item != '(' && comp( op->item, s[ i ] ) >= 0 )
				{
					if( !pop( data, a ) || !pop( data, b ) )
					{
						reportError();
					}
					pop( op, oper );
					push( data, cal( b, a, oper ) );
					push( op, s[ i ] );
				}
				else
					push( op, s[ i ] );
			}
		}
	}

	if( !data )
	{
		reportError();
	}
	pop( data, a );
	if( data )
	{
		reportError();
	}
	return a;
}