expression.cpp

本程序实现的是以树型方式存储的表达式的各种操作

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include "expression.h"
//摧毁表达式函数
void DestroyExpr(BiTree &E )
{
	if( E )
	{
		DestroyExpr( E->lchild );
		DestroyExpr( E->rchild );
		free(E);
	}
	E = NULL;
}
//输入表达式函数
int ReadExpr(BiTree &T)
{
	if( !T )
		DestroyExpr(T);
	char e;
	e=getchar();	     
	if(e=='+'||e=='-'||e=='*'||e=='/'||e=='^')   //如果输入的是符号，则进行递归调用
	{
		T=(BiTree)malloc(sizeof(LNode));
		(T->data).oper=e;
		T->tag=0;
		if(!ReadExpr(T->lchild)) return 0;    //先进行左子树的递归操作
		if(!ReadExpr(T->rchild)) return 0;    //再进行右子树的递归操作
	}
	else
	{
		if(e>='0'&&e<='9'||e>='a'&&e<='z')    //如果输入的变量合法，则给树叶节点赋值
		{
			T=(BiTree)malloc(sizeof(LNode));
			T->lchild=NULL; T->rchild=NULL;
			if(e>='0'&&e<='9')
			{
				T->data.num=e-'0';
				T->tag=1;
			}
			else
			{
				(T->data).oper=e;
				T->tag=2;
			}
		}
		else                               //若输入的变量不合法则提示输入错误
			printf("输入错误\n");
	}
	return 1;
}
//操作符优先比较函数
int Compare(char a,char b)    
{
	if( ((a=='*' || a=='/') && (b=='+' || b=='-')) || a=='^' && b!='^')
		return 1;
	else
		return 0;
}
//表达式输出函数
int WriteExpr(BiTree T)
{
	if( !T )
		return 1;
	int p,q;
	if(T->tag == 0)
	{
		if( !T->lchild || !T->rchild )   //当树的左右孩子树均空时返回
			return 0;
		p = T->lchild->tag;
		if((p == 0)&&Compare(T->data.oper,T->lchild->data.oper))
		{
			printf("(");   //比较符号的优先关系，从而判断是否要进行添加括号的操作
			if(!WriteExpr(T->lchild)) return 1;
			printf(")");
		}
		else if( !WriteExpr( T->lchild) )   //如不需要添加括号则直接进行递归调用
			return 0;
		printf("%c",(T->data).oper);
        q = T->rchild->tag;  //右子树也进行如上的操作
		if((q == 0)&&Compare(T->data.oper,T->rchild->data.oper))
		{ 
			printf("(");
			if( !WriteExpr( T->rchild) ) return 0;
			printf(")");
		}  
		else if( !WriteExpr( T->rchild) ) 
			return 0;
	}
	else    //当调用到叶子节点时进行如下操作
	{
		if(T->tag==1)
		{
			if(T->data.num<0)
			{
				printf("(");
				printf("%d",T->data.num);
				printf(")");
			}
			else
				printf("%d",T->data.num);
		}
		else
			printf("%c",(T->data).oper);
	}
	return 1;
}
//变量赋值函数
int Assign(BiTree &T,char V,int c)
{
	if(T->tag==0)
	{
		if(!Assign(T->lchild,V,c)) return 1;   //递归调用查找叶子节点
		if(!Assign(T->rchild,V,c)) return 1;
	}
	else       //当找到叶子节点后进行变量的赋值操作
		if(T->tag==2 && T->data.oper==V)
		{
			T->data.num=c;
			T->tag=1;
		}
	return 1;
}
//表达式求值函数
int Value(BiTree &T)
{
	char oper;
	int i;
	int a,b,sum;
	if(T->tag == 0)
	{
		oper=T->data.oper;
		a=Value(T->lchild);   //递归调用求值函数在求树T的左右孩子树的值
		b=Value(T->rchild);
	}
	else
		return T->data.num;
	switch(oper)    //根据运算符进行相应的运算操作
	{
		case '+':return(a+b);
		case '-':return(a-b);
		case '*':return(a*b);
		case '/':return(a/b);
		case '^':sum=a;
				 for(i=1;i<b;++i)
					 sum*=a;
				 return(sum);
	}
	return 0;
}
//构造复合表达式函数
BiTree CompoundExpr(char p,BiTree E1,BiTree E2)
{
	BiTree E;
	E=(BiTree)malloc(sizeof(LNode));
	E->lchild=E1;          //将E的左孩子设为E1，右孩子设为E2
	E->rchild=E2;
	E->data.oper=p;
	E->tag = 0;
	return E;
}
//合并常数项的函数
int MergeConst(BiTree &T)
{
	BiTree p,q;
	if( T->lchild->tag == 0 )   //若左子树的数据为操作符，则递归调用合并函数
		MergeConst(T->lchild);
	if( T->rchild->tag == 0 )   //若右子树的数据为操作符，则递归调用合并函数
		MergeConst(T->rchild);
	if( T->lchild->tag == 1 && T->rchild->tag == 1 )  //若左右孩子均为数字，则进行合并操作
	{
		p=T->lchild;
		q=T->rchild;
		T->data.num = Value(T);
		T->tag = 1;   //将该节点标记为数字节点
		free(p);   //释放无用的子节点
		free(q);
	}
	return 0;
}