#include
#include
#include
#include?
#include?

#define?ERROR?0
#define?OK?1
#define?TRUE?1
#define?FALSE?0
#define?MAXSIZE?100
#define?MAXINT	65535
typedef?char?TElemType;
typedef?TElemType?EElemType;
typedef?enum{OperatorConstantVariable}ElemTag;//Operator==0:運算符constant==1:常量Variable==2:變量
//不帶頭結點的二叉鏈表存儲表示
typedef?struct?BiTNode
{
	ElemTag?tag;							//用于區別操作數和運算符
	EElemType?data;							//數據域
	int?value;								//值域若元素類型為常量或變量則用來記錄它的值，運算符則用來記錄兩子樹運算后的結果
	struct?BiTNode?*lchild*rchild;			//孩子結點的指針
}BiTNode*BiTree;

typedef?BiTree?Expr;
typedef?int?Status;


void?Assign（Expr?&EEElemType?Vint?c）
{
	//實現對變量V的賦值（V=c）變量的初值為0
	//先序遍歷整棵樹把數據域為V的結點賦值為c
	if（!E）return;
	if（E->data==V）E->value=c;
	Assign（E->lchildVc）;
	Assign（E->rchildVc）;
}


Expr?CompoundExpr（EElemType?PExpr?&E1Expr?E2）
{
	//構造一個新的符合表達式（E1）P（E2）
	BiTNode?*p;
	if（!（p=（BiTNode*）malloc（sizeof（BiTNode））））return?NULL;
	p->lchild=E1;				//運算符的左孩子
	p->rchild=E2;				//運算符的右孩子
	p->tag=Operator;
	p->data=P;
	return?p;
}


Status?Destroy（Expr?&T）
{
	if（!T）return?OK;
	Destroy（T->lchild）;
	Destroy（T->rchild）;
	free（T）;
	T=NULL;
	return?OK;
}


Status?Exist（Expr?EEElemType?e）
{
	//判斷表達式E是否存在變量e存在返回TRUE，否則返回FALSE
	if（!E||e<‘a‘||e>‘z‘）return?FALSE;	//不是變量則返回錯誤
	if（E->data==e）return?TRUE;
	return?Exist（E->lchilde）||Exist（E->rchilde）;?//遞歸尋找e
}


Status?Diff（Expr?&EEElemType?v）
{
	//先序遍歷整個表達式E對變量v進行求導
	BiTNode?*p*q;
	if（!E||E->tag!=Operator）return?OK;
	p=E;
	if（Exist（Ev））	//如果子孫中有變量v
	{
		if（E->data==‘^‘）					//若當前結點為‘^‘
		{
			
			//交換右子樹賦值給左子樹
			p=E->lchild;
			E->lchild=E->rchild;
			E->data=‘*‘;		//當前運算符變為*
			//右子樹變為原來表達式指數-1的情況				
			if（!（q=（BiTNode*）malloc（sizeof（BiTNode））））return（OVERFLOW）;
			q->tag=Operator;	//右子樹根結點
			q->data=‘^‘;
			q->value=MAXINT;
			q->lchild=p;		//右子樹的左孩子是當前結點原來的左子樹	
			if（!（p=（BiTNode*）malloc（sizeof（BiTNode））））return（OVERFLOW）;
			p->tag=Constant;		//右子樹的右孩子
			p->data=E->lchild->data-1;
			p->value=E->lchild->value-1;
			p->lchild=p->rchild=NULL;
			q->rchild=p;
			E->rchild=q;
			p=E->rchild;
		}
		else?if（E->data==‘*‘）		////若當前結點為‘*‘
		{
			if（E->rchild->data==v）	//右孩子直接為變量v，則求導后v的指數為0
			{		
				free（E->rchild）;	//刪除右結點
				p=E;
				E=E->lchild;	//把左孩子成為根結點
				free（p）;
				p=E;
			}
			//其的情況則最后合并常數則可以
		}
		else?
		{
			if（!Exist（E->lchildv））q=E->lchild;	//若左孩子或右孩子沒有變量，則左孩子或右孩子變成常數0
			if（!Exist（E->rchildv））q=E->rchild;
			q->data=‘0‘;
			q->value=0;
			q->lchild=q->rchild=NULL;
		}
	}
	else?	//不存在變量則把整個樹刪除，留下根結點?
	{
		Destroy（E->lchild）;			//刪除左右子樹
		Destroy（E->rchild）;
		E->tag=Constant;			//根結點為常數0
		E->data=‘0‘;
		E->value=0;
	}
		Diff（p->lchildv）;				//遞歸左右子樹
		Diff（p->rchildv）;	
	return?OK;
}


int?Value（Expr?&E）
{	
	//后根遍歷對表達式求值
	int?ab;
	if（E->tag!=Operator）return?E->value;
	a=Value（E->lchild）;
	b=Value（E->rchild）;
	if（a==MAXINT||b==MAXINT）

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2015-06-26?21:19??表達式類型的實現\
?????文件???????????8??2015-06-20?23:03??表達式類型的實現\1.txt
?????文件???????16675??2015-07-10?12:20??表達式類型的實現\expression.cpp
?????文件??????225323??2015-06-20?22:30??表達式類型的實現\expression.exe
?????文件????????1131??2015-06-20?23:18??表達式類型的實現\測試數據.txt
?????文件??????519942??2015-07-10?12:19??表達式類型的實現\表達式類型的實現課程設計報告.doc