expression evaluation.cpp

1.表达式求值；2.二分匹配模板；3.最大流；4.点到线段的距离；5.字符串字典顺序

//自己写的表达式求值，暂时不能处理负数 。 整型运算 
//07-8-23 

#include <stdio.h>
#include <string.h>

int prece( char c1) 
{
	if ( c1 == '+' || c1 =='-' ) return 1;
	if ( c1=='*'|| c1=='/' ) return 2;
	if ( c1 =='(' ) return -1;
	return 0;
} 
void  pre_to_postfix (int cnt , char str[] , char exp[] )
{
		char  stk [ 200 ];
	int top = 0 , tmp, num , len = strlen ( str ) , j  ;	
	char tc;
	cnt = 0 ;	
	for ( int i = 0 ; i < len ;   ) 
	{
		if ( str [ i ] ==' ' ){  continue;  i ++ ; }  
	    if ( ! ( str [ i ]>=48 && str [ i ]<=57 )  )
	    {
			if ( top ==0 ) { stk [ top ++ ] = str [ i ++] ;  continue; } 
			if ( str [i ] =='(' ) 
				 stk [ top ++ ] = str [ i ++ ]; 
			
			else if (  str [i ] ==')'  ) 
			{
				while ( stk [ top -1 ] != '('  && top > 0  ) 		
				{  exp [ cnt ++ ] = stk [ -- top ] ;  }
				if ( top > 0 && stk [ top-1 ] =='('  ) top --;
				i ++ ;
			}
			else
			{
				if ( prece( str [ i ] ) > prece ( stk[ top-1 ] ) )
					stk [ top ++ ] = str [ i ++ ];
				else exp [ cnt++ ] = stk [ -- top ] ;
			}	
			continue; 	
		}   
		while   ( str [ i ]>=48 && str [ i ]<= 57  && i < len ) 
			exp [ cnt++ ] =  str[ i ++ ]  ;
		exp [ cnt ++ ] = '#'  ;	 	
	}
	while ( top > 0 ) 
		exp [ cnt ++ ] = stk [ -- top ] ; 

	exp [ cnt ] = '\0' ;
}

int calculate ( int len , char exp[] )
{
	int ans = 0 , num = 0 , i = 0 , j  = 0 , stk [ 100 ] , top = 0 ;
	while ( i <len ) 
	{
		if ( exp [ i ] >= 48 && exp [ i ] <= 57 ) 	
		{	
			num = 0  , j = i ; 
			while (exp [ j ] >= 48 && exp [ j  ] <= 57  && j < len ) 
				num = num * 10 +  ( exp [ j ++ ]- 48 ) ;
			stk [ top ++ ] = num , i = j + 1 ;
		}
		else
		{
			switch ( exp [ i ] ) 
			{
				case '+': stk [ top- 2   ]= stk [ top - 2 ] + stk [ top - 1  ] ;  
						break; 
				case '-' : stk [ top-2 ] = stk [ top -2 ] - stk [ top - 1 ] ;
						break;
				case '*': stk [ top -2 ] = stk [ top - 2 ] * stk [ top - 1 ] ; 
						break;
				case '/' : stk [ top -2 ] = stk [ top - 2 ] / stk [ top - 1 ];
						break;
			}	
			i ++ ;  top --;
		}
	}
	return stk [ top -1 ] ;
}

int main()
{
	char str [ 100 ];
	while ( scanf("%s",str ) )
	{
		char  exp [ 100 ] ; 
		int len = 0 , ans  ;
		pre_to_postfix( len , str, exp );
	//	printf("%s\n",exp);	
		len = strlen ( exp) ;
		ans =	calculate ( len , exp ) ;
		printf("%d\n", ans ) ;
	}
	return 0;	
}