表达式求值(以@结尾的中缀算术表达式)

[c++]代码库

#include<iostream.h>
#include<stdlib.h>
#include<ctype.h>
#include<PROCESS.H>
#include<STRSTREAM.H>
typedef float elemtype;
struct stack
{
	elemtype *stack;
	short top;
	short stackmaxsize;
};

static void initstack ( stack &s,int ms )
{
	s.stack=new elemtype[ms];
	if ( !s.stack )
	{
		cerr<<"memory full!"<<endl;
		exit ( 1 );
	}
	s.top=-1;
	s.stackmaxsize=ms;
}

static void  clearstack ( stack &s )
{ s.top=-1;}

static void  deletestack ( stack &s )
{
	delete []s.stack;
	s.top=-1;
	s.stackmaxsize=0;
}

static int  stackempty ( stack &s )
{ return s.top==-1;}

static elemtype  peek ( stack &s )
{
	if ( s.top==-1 )
	{
		cerr<<"stack empty!"<<endl;
		exit ( 1 );
	}
	return s.stack[s.top];
}

static void push ( stack &s,elemtype itim )
{
	if ( s.top==s.stackmaxsize-1 )
	{
		cerr<<"stack ovflw!"<<endl;
		exit ( 1 );
	}
	s.top++;
	s.stack[s.top]=itim;
}

static elemtype pop ( stack &s )
{
	if ( s.top==-1 )
	{
		cerr<<"stack empty!"<<endl;
		exit ( 1 );
	}
	s.top--;
	return s.stack[s.top+1];
}

static int stackfull ( stack &s )
{
	return s.top==s.stackmaxsize-1;
}

int precedence ( char op )
{
	switch ( op )
	{
	case'+':
	case'-':
		return 1;
	case'*':
	case'/':
		return 2;
	case'(':
	case'@':
	default:
		return 0;
	}
}


static float compute ( char *str )
{
	typedef float elemtype;
	int sm=20;
	stack s;
	initstack ( s,sm );
	istrstream ins ( str );
	char ch;
	float x;
	ins>>ch;
	while ( ch!='@' )
	{
		switch ( ch )
		{
		case'+':
			x=pop ( s ) +pop ( s );
			break;
		case'-':
			x=pop ( s );
			x=pop ( s )-x;
			break;
		case'*':
			x=pop ( s ) *pop ( s );
			break;
		case'/':
			x=pop ( s );
			if ( x!=0 )
				x=pop ( s ) /x;
			else
			{
				cerr<<"divide by 0!"<<endl;
				exit ( 1 );
			}
			break;
		default:
			ins.putback ( ch );
			ins>>x;
		}
		push ( s,x );
		ins>>ch;
	}
//	 x=pop(s);
//	 return x;
	if ( !stackempty ( s ) )
	{
		x=pop ( s );
		if ( !stackempty ( s ) )
		{
			cerr<<"expression error!"<<endl;
			exit ( 1 );
		}
	}
	else
	{
		cerr<<"stack is empty!"<<endl;
		exit ( 1 );
	}
	return x;
}

static void change ( char *s1,char  *s2 )
{
	typedef char elemtype;
	int ms=20;
	stack r;
	initstack ( r,ms );
	push ( r,'@' );
	int i,j;
	i=0;
	j=0;
	char ch=s1[i];
	while ( ch!='@' )
	{
		if ( ch==' ' )
			ch=s1[++i];
		else if ( ch=='(' )
		{
			push ( r,ch );
			ch=s1[++i];
		}
		else if ( ch==')' )
		{
			while ( peek ( r ) !='(' )
				s2[j++]=pop ( r );
			pop ( r );
			ch=s1[++i];
		}
		else if ( ch=='+'||ch=='-'||ch=='*'||ch=='/' )
		{
			char w=peek ( r );
			while ( precedence ( w ) >=precedence ( ch ) )
			{
				s2[j++]=w;
				pop ( r );
				w=peek ( r );
			}
			push ( r,ch );
			ch=s1[++i];
		}
		else
		{
			while ( isdigit ( ch ) ||ch=='.' )
			{
				s2[j++]=ch;
				ch=s1[++i];
			}
			s2[j++]=' ';
		}
	}
	ch=pop ( r );
	while ( ch!='@' )
	{
		if ( ch=='(' )
		{
			cerr<<"expression error!"<<endl;
			exit ( 1 );
		}
		else
		{
			s2[j++]=ch;
			ch=pop ( r );
		}
	}
	s2[j++]='@';
	s2[j++]='\0';
}

void main()
{
	char a[50],b[50];
	cout<<"input in @ end :"<<endl;
	cin.getline ( a,sizeof ( a ) );
	change ( a,b );
	cout<<"dui ying de hou zhui biao da shi:"<<endl;
	cout<<b<<endl;
	cout<<"qiu zhi jie guo shi:"
	    <<compute ( b ) <<endl;
}