expr.cpp

数据结构课程设计,表达式,用C语言实现,难度系数较高

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h> 
//#include "../header/bitree.h"
#include "../header/queue.h"
#include "../header/stack.h"
#include "../header/expr.h"

	
int Random( int   nMin, int   nMax )
//返回nMin到nMax之间的随机数
//原想用random(n);可vc里面没有
{   
	srand( ( unsigned ) time ( NULL ) );   
	return rand() % ( nMax - nMin ) + nMin;
}

Status IsRepeat( char *c, int j, char str )
//字符str是否c数组里的前j个元素字符相同
//是的话返回TRUE，否则返回FALSE
//为了简化void FindVary( char *c, char * e )
{
	for( int i = 0; i < j; ++i )
		if( c[i] == str )
			return TRUE;      //重复
	return FALSE;
}

void FindVary( char *c, char * e )
//找出表达式中的变量
{
	int i = -1, j = 0;
	while( e[++i] )
		if( e[i] >= 'A' && e[i] <= 'Z' || e[i] >= 'a' && e[i] <= 'z' )
			if( ! j || ! IsRepeat( c, j, e[i] ) )		//j == 0||不重复
				if( e[i] == 's' && e[i+1] == 'i' && e[i+2] == 'n' ||//sin
					e[i] == 'S' && e[i+1] == 'I' && e[i+2] == 'N' ||
					e[i] == 'c' && e[i+1] == 'o' && e[i+2] == 's' ||//cos
					e[i] == 'C' && e[i+1] == 'O' && e[i+2] == 'S' ||
					e[i] == 't' && e[i+1] == 'a' && e[i+2] == 'n' ||//tan
					e[i] == 'T' && e[i+1] == 'A' && e[i+2] == 'N'  )
				{
					i += 2;
					continue;
				}
				else
					c[j++] = e[i];
	c[j] = 0;
}

Status Visit( ExpTree e )
//输出e的内容
{
	int m, n[5];
	if( e->tag == OPER )				//运算符
			printf("%s", e->expr );
	else if( e->tag == VAR )			//变量
	{
		if( !e->vary.val )			//变量的值是0
			printf("%c",    e->vary.var );//输出变量名
		else
			printf("%0.4f", e->vary.val );//输出变量的值
	}
	else								//常量
	{
		if( e->ordina >= 0 )				//正数
			printf("%d", e->ordina );
		else
			printf("(%d)", e->ordina );		//负数，输出时加括号
	}
	return OK;
}

Status ArrayCreateExp( ExpTree &E, char *ch, int &i )
//从ch数组中读取字符串，构造表达式
{
	if( ch[i] )
	{
		if( ! ( E = ( ExpTree )malloc( sizeof( ExpNode ) ) ) )
			return ERROR; 
		if( ch[i] == 's' && ch[i+1] == 'i' && ch[i+2] == 'n' ||//sin
			ch[i] == 'S' && ch[i+1] == 'I' && ch[i+2] == 'N' ||
			ch[i] == 'c' && ch[i+1] == 'o' && ch[i+2] == 's' ||//cos
			ch[i] == 'C' && ch[i+1] == 'O' && ch[i+2] == 'S' ||
			ch[i] == 't' && ch[i+1] == 'a' && ch[i+2] == 'n' ||//tan
			ch[i] == 'T' && ch[i+1] == 'A' && ch[i+2] == 'N'  )
		{
			E->tag = OPER;
			E->expr[0] = ch[i];	E->expr[1] = ch[++i];	E->expr[2] = ch[++i];
			E->expr[3] = '\0';
			ArrayCreateExp( E->rchild, ch, ++i );//只建右子树
			E->lchild = NULL;					 //左子树为空
			return OK;
		}
		else if( ch[i] >= '0' && ch[i] <= '9' )		//数字
		{
			E->tag = ORD;
			E->ordina = ch[i] - '0';
		}
		else if( ch[i] >= 'a' && ch[i] <= 'z' )	    //变量
		{
			E->tag = VAR;
			E->vary.var = ch[i];
			E->vary.val = 0;
		}
		else if( ch[i] == '+' || ch[i] == '-' || ch[i] == '*' || ch[i] == '/' || ch[i] == '^' )//运算符
		{
			E->tag = OPER;
			E->expr[0] = ch[i];
			E->expr[1] = '\0';
		}
		if( ! E->tag )			// E 是运算符
		{
			ArrayCreateExp( E->lchild, ch, ++i ); 
			ArrayCreateExp( E->rchild, ch, ++i ); 
		}
		else
		{
			E->lchild = NULL;
			E->rchild = NULL;
		}
	}
	return OK;
}

Status InputCreateExp( ExpTree &E )  
//从键盘先序输入来构造表达式
//数字范围：0-9
//变量范围：a-z
//运算符范围： '+' ,'-','*', '/' ,'^' 
{   

	char ch;   
    scanf( "%c", &ch );
	if( ch )
	{
		if( ! ( E = ( ExpTree ) malloc( sizeof ( ExpNode ) ) ) )
			return ERROR; 
		if( ch >= '0' && ch <= '9' )		//数字
		{
			E->tag = ORD;
			E->ordina = ch - '0';
		}
		else if( ch >= 'a' && ch <= 'z' )	//变量
		{
			E->tag = VAR;
			E->vary.var = ch;
			E->vary.val = 0;
		}
		else if( ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^' )//运算符
		{
			E->tag = OPER;
			E->expr[0] = ch;
			E->expr[1] = '\0';
		}
		if( ! E->tag )						//E是运算符
		{
			InputCreateExp( E->lchild ); 
			InputCreateExp( E->rchild ); 
		}
		else
		{
			E->lchild = NULL;
			E->rchild = NULL;
		}
	}
	return OK;
}

void CreateExp( ExpTree &E, char *ch, int &i ) 
//调用Status ArrayCreateExp( BiTree &T, char *ch, int &i )
//从ch数组中读取字符串，构造表达式，并用中缀表示式输出
{
	i = 0;//CreateExp( T, ch[i], j=0);也可以
	if( ArrayCreateExp( E, ch, i ) )
	{
		printf("中缀表示式输出：");
		InorderExp( E, Visit );		//输出中序表达式
		printf("\n");
	}
	else
		printf("构造表达式树失败！");
}

int power( int a, int b )		//返回a^b
{
	long pow = 1;
	for( int i = 0; i < b; ++i )
		pow *= a;
	return pow;
}

/*当根结点和左（右）孩子都是运算符时，
比较优先级，当前者优先级高于后者时，需要加括号。*/
int precede( ExpTree e1, ExpTree e2 )		//比较两运算符e1和e2的优先级
{
	if( e1->tag || e2->tag )	//不是运算符
		return (-1);
	switch( e1->expr[0] )
	{
		case '+':
		case '-':
			if( e2->expr[0] == '+' || e2->expr[0] == '-' )
				return (0);
			else
				return (-1);
		case '*':
		case '/':
		case '^':
		case 's':
		case 'c':
		case 't':
			if( e2->expr[0] == '*' || e2->expr[0] == '/' || e2->expr[0] == '^' 
			 || e2->expr[0] == 's' || e2->expr[0] == 'c' || e2->expr[0] == 't' )
				return (0);
			else
				return (1);
	}
}



void InorderExp( ExpTree E, Status ( * Visit )( ExpTree e ) )
//输出中序表达式用带括号的中缀表示式输出
{
	int bracket;
	if( E )
	{
		if( E->lchild )
		{
			bracket = precede( E, E->lchild );//比较双亲与左孩子运算符优先级
			if( bracket > 0 )							  //左孩子优先级低
				printf("(");
			InorderExp( E->lchild, Visit );
			if( bracket > 0 )	
				printf(")");
		}
		Visit( E );
		if( E->rchild )
		{
			bracket = precede( E, E->rchild );//比较双亲与右孩子运算符优先级
			if( bracket >= 0 )							  //右孩子优先级低
				printf("(");							 
			InorderExp( E->rchild, Visit );
			if( bracket >= 0 )	
				printf(")");
		}
	}
}

ExpTree FindVarNode( ExpTree E, char x)    
//返回变量域为x结点的指针 
{
	ExpTree p;
	if( !E )	return NULL ;
	else if( E->tag == VAR && E->vary.var == x )		return E;
	else
	{
		p = FindVarNode( E->lchild, x );           //在左子树中找
		if( !p )							//在左子树中找不到
			p = FindVarNode( E->rchild, x );   //在右子树中找
		return	p;
	}
}

Status BTAssign( ExpTree &E, char v, float e )
//初始条件：二叉树T存在，E是T中某个结点。
//操作结果：返回E的值。
{
	if( !E )	return FALSE;			//是空树	
	if( E->tag == VAR && E->vary.var == v && ! E->vary.val )		//找到了
	{
		E->vary.val = e;
		return OK;
	}
	if( ! BTAssign( E->lchild, v, e ) )					//在左子树中找不到
		if( ! BTAssign( E->rchild, v, e ) )				//在右子树中找不到
			return FALSE;				
	return	OK;
}

Status Assign( ExpTree E, char v, float c ) 
//多次对T赋值，弥补原来BTAssign( T, e,value )函数只有一次赋值的缺点
//对表达式内的所有v，赋值c
{
	for( int flag = 0; BTAssign( E, v, c ); flag++ );
	return flag;
}


float Value( ExpTree E )
//计算表达式的值
{
	float lv,rv,value = 0;
	if( E )
	{
		if( E->tag == VAR )			//变量
			return ( E->vary.val );
		if( E->tag == ORD )         //常量
			return ( E->ordina );
		if( E->lchild )		lv = Value( E->lchild );
		rv = Value( E->rchild );
		switch( E->expr[0] )
		{
			case '+': value = lv + rv; break;
			case '-': value = lv - rv; break;
			case '*': value = lv * rv; break;
			case '/': if( rv ) value = lv / rv; 
						else exit( 0 );
						break;
			case '^': value = power( lv, rv ); break;
			case 'S': case 's': value = sin( rv ); break;//sin
			case 'T': case 't': value = tan( rv ); break;//tan
			case 'C': case 'c':
				if( E->expr[2] == 'S' || E->expr[2] == 's' )//cos
				{	value = cos( rv ); 
					break;
				}
		}
	}
	return ( value );
}

Status CopyBiTree( ExpTree &e1, ExpTree e2 )
//e1复制成e2
{
	if( e2 )
	{
		if( ! ( e1 = ( ExpTree ) malloc ( sizeof( ExpNode ) ) ) )
			return FALSE;
		e1->tag = e2->tag;
		if( e2->tag == OPER )		e1->expr[0] = e2->expr[0];
		else if( e2->tag == VAR ){	e1->vary.var = e2->vary.var;e1->vary.val = e2->vary.val; }
		else e1->ordina = e2->ordina;
		if( !e2->lchild )
			e1->lchild = NULL; 
		else if( ! CopyBiTree( e1->lchild, e2->lchild ) )
			return FALSE;
		if( !e2->rchild )
			e1->rchild = NULL;
		else if( ! CopyBiTree( e1->rchild, e2->rchild ) )
			return FALSE;
		return OK;
	}
	else
		e1 = NULL;
}

ExpTree Compound( char p, ExpTree e1, ExpTree e2 )	
//5.构造一个新的复合表达式(E1)P(E2)			
{
	ExpTree E;
	if( ! ( E = ( ExpTree ) malloc ( sizeof ( ExpNode ) ) ) )
		return ERROR;
	E->tag = OPER;
	E->expr[0] = p;
	E->expr[1] = 0;
	E->lchild = e1;	
	E->rchild = e2;
	return E;
}

Status Diff( ExpTree &E, char V )
//求偏导函数Diff(E,V)
{
	ExpTree e,P;
	if( ! E )	return FALSE;//叶子
	if( E->lchild )		Diff( E->lchild, V );
	if( E->rchild )		Diff( E->rchild, V );	
	if( E->rchild && E->rchild->lchild && E->rchild->lchild->tag == VAR && E->rchild->lchild->vary.var == V )//E的左孩子是变量且==V
	{
		if( E->rchild->rchild->tag == ORD )		//指数是常量
		{
			if( E->tag == OPER && E->expr[0] == '*' )		//前一个运算符是'*'
			{
				if( E->lchild->tag == ORD )		//前一个乘项是常量
				{
					E->lchild->ordina *= E->rchild->rchild->ordina;
					E->rchild->rchild->ordina --;
				}
				else//前一项是变量或者是表达式
				{
					e = ( ExpTree ) malloc ( sizeof ( ExpNode ) );
					e->lchild = E->lchild;
					e->rchild = ( ExpTree ) malloc ( sizeof ( ExpNode ) );
					e->rchild->tag = ORD;
					e->rchild->ordina = E->rchild->rchild->ordina;
					E->rchild->rchild->ordina --;
					e->rchild->lchild = NULL;
					e->rchild->rchild = NULL;
				}
			}
			else if( E->tag == VAR && E->expr[0] == '+' )//前一个运算符是'+' 
			{
				e = ( ExpTree ) malloc ( sizeof ( ExpNode ) );
				e->rchild = E->rchild;
				e->tag = ORD;
				e->lchild = ( ExpTree ) malloc ( sizeof( ExpNode ) );
				e->lchild->tag = ORD;
				e->lchild->ordina = E->rchild->rchild->ordina;
				E->rchild->rchild->ordina --;
				e->lchild->lchild = NULL;
				e->lchild->rchild = NULL;
			}
		}
	}
	
	else if( E->tag == OPER && ( E->expr[0] == '+' || E->expr[0] == '-' ) )//'+','-'
	{
		if( E->lchild->tag == VAR && E->lchild->vary.var == V )
		{
			E->lchild->tag = ORD;
			E->lchild->ordina = 1;
		}
		else if( E->rchild->tag == VAR && E->rchild->vary.var == V )
		{
			E->rchild->tag = ORD;
			E->rchild->ordina = 1;
		}
		else if( E->lchild->tag == ORD )
		{
			free( E->lchild );
			e = E;
			E = E->rchild;
			free( e );
		}
		else if( E->rchild->tag == ORD )
		{
			free( E->rchild );
			e = E;
			E = E->lchild;
			free( e );
		}
	}
	if( E->rchild && E->rchild->tag == OPER &&  E->rchild->expr[0] == '*'  ) 
	{
		if(  E->rchild->rchild->tag == VAR && E->rchild->rchild->vary.var == V )
		{
			if( E->rchild->lchild->tag == ORD )
			{
				E->rchild->tag = ORD;
				E->rchild->ordina = E->rchild->lchild->ordina;
				free( E->rchild->lchild );
				E->rchild->lchild = NULL;
				free( E->rchild->rchild );
				E->rchild->rchild = NULL;
			}
		}
	}
}

void MergeConst( ExpTree E )
//合并表达式种所有常数运算
{	
	if( ! E->lchild && ! E->rchild )	return;		//叶子
	if( E->tag == OPER && E->lchild && E->rchild && E->lchild->tag == ORD && E->rchild->tag == ORD )
	{
		E->tag = ORD;
		switch( E->expr[0] )
		{
		case '*':
			E->ordina = E->lchild->ordina * E->rchild->ordina;			break;
		case '/':
			E->ordina = E->lchild->ordina / E->rchild->ordina;			break;
		case '^':
			E->ordina = power( E->lchild->ordina, E->rchild->ordina );	break;
		case '+':
			E->ordina = E->lchild->ordina + E->rchild->ordina;			break;
		case '-':
			E->ordina = E->lchild->ordina - E->rchild->ordina;			break;
		}
		free( E->lchild );
		free( E->rchild );
		E->lchild = NULL;
		E->rchild = NULL;
	}
	else
	{
		if( E->lchild )
			MergeConst( E->lchild );
		if( E->rchild )
			MergeConst( E->rchild );
	}
}

Status PreOrderTraverse( ExpTree E, Status ( * Visit )( ExpTree e ) )
//波兰式输出
//前序遍历的递归算法   
{   
	if( E )   
	{     
		if( Visit( E ) )
			if( PreOrderTraverse( E->lchild, Visit ) )   
				if( PreOrderTraverse( E->rchild, Visit ) )
					return OK;
		return ERROR;
	}
	else
		return OK;
}

Status PostOrderTraverse( ExpTree E, Status ( * Visit )( ExpTree e ) )
//逆波兰式输出
//树的后序遍历的递归算法
{   
	if( E )   
	{     
		if( PostOrderTraverse( E->lchild, Visit ) )
			if( PostOrderTraverse( E->rchild, Visit ) )   
				if(  Visit( E ) )
					return OK;
		return ERROR;
	}
	else
		return OK;
}