typedef int   TElemType;                    // 樹結點數據域類型為整型 
typedef float OElemType;                    // 操作數類型為浮點型

typedef struct BiTNode{                     // 二叉樹的類型定義 
   TElemType    data;
   struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

typedef union {
	char  OPTR;                        // SElemType 可以字符也可以是 二叉樹的結點   
	BiTree  BiT; 
} SElemType;

#include"stack.h"

/************************* 出錯信息處理函數定義 ***********************/
 
void ERRORMESSAGE(char *s)                 
{
   cout<<s<<endl;
   exit(1);
} //ERRORMESSAGE

/*************************** 輸入數據的操作 ***********************/
void GetExp(char *Exp)
{//得到一個表達式,并對其進行單目運算的模式匹配
	char ch;
	int n=FALSE, i=0;
	do
	{
		cin>>ch;
 		if (n==TRUE && (ch=='-' || ch=='+'))   Exp[i++]='0';
		else n=FALSE;
		Exp[i++]=ch;
		if (ch=='(') n=TRUE;  
	}
	while (ch!='#');
	Exp[i]='\0';
}//GetExp
 
/********************表達式樹的相關操作 *******************/ 

status IN(char ch,char *OP)
{
	//判斷字符ch 是否屬于運算符集
	char *p=OP;
	while (*p && ch!=*p ) ++p;
	if (!*p) return ERROR;
	return OK;
}//IN


void ChangeOPND( char *p ,int pos, int &n, OElemType *operand)
{
	//把相應的字符串轉成對應的運算數,并存入operand數組中,pos是operand中的位序
	//使用 atof 系統函數進行轉換.
	char data[MAX_OPERAND], *q = data; 
	n=0;
	while ((*p<='9' && *p>='0') || (*p=='.'))
	{
		*q++=*p++;
		n++;
	}
	*q = '\0';
	operand[pos] = (float)atof(data);
}//ChangeOPND

void CrtNode(BiTree &T,int position ,Stack &PTR)
{
	// 建葉子結點^T, 結點中的數據項為操作數所在的operand數組中的位置
    // 建立完成后把結點裝入PTR棧
	SElemType e;
	T = new BiTNode;
	T->data = position;
	T->lchild = T->rchild = NULL;
	e.BiT = T;
	Push(PTR, e);
}//CrtNode

int ChangeOPTR(char ch)
{
	// 把相應的操作符轉成宏定義值
	int n;
	if (ch=='+') n = PLUS;
	else if (ch=='-') n = MINUS;
		 else if(ch=='*') n = ASTERISK;
			  else if(ch=='/') n = SLANT;
	return n;
}//ChangeOPTR

void CrtSubtree (BiTree &T, char ch, Stack &PTR) 
{
	// 建子樹^T, 其中根結點的數據項為操作符
    SElemType e;
	T = new BiTNode;
	T->data = ChangeOPTR(ch);
	if (Pop(PTR, e))  T->rchild = e.BiT;
	else T->rchild = NULL;
	if (Pop(PTR, e))  T->lchild = e.BiT;
	else T->lchild = NULL;
	e.BiT = T;
	Push(PTR, e);
}//CrtSubtree

status precede(char c,char ch)
{
	//算符間的優先關系表,此表表示兩操作符之間的大于小于關系
  	switch (c)
	{
	case '#':   
	case '(':	return ERROR;
	case '*':
	case '/':					
	case '+':
	case '-':	if (!(ch!='*' && ch!='/')) return ERROR;
				return OK;
	default :	return OK;
	}
}//precede

void CrtExptree(BiTree &t, char *exp, OElemType *operand, char *operate) 
{
	// 建立由合法的表達式字符串確定的只含二元操作符的
	// 非空表達式樹，其存儲結構為二叉鏈表

	SElemType e,c;
	char *p,ch;
	int pos=0,n;
 
	Stack S_OPTR,S_BiT;		// 棧S_OPTR內放表達式的操作符,棧S_BiT放生成的結點					
	InitStack(S_OPTR); 
	e.OPTR = '#';
	Push(S_OPTR,e);						// 把字符#進棧
	InitStack(S_BiT);
	
	p = exp;  ch = *p;                       // 指針p指向表達式
	GetTop(S_OPTR,e);
	while (!(e.OPTR=='#' && ch=='#'))            // 當從棧S_OPTR退出的操作符為#,且ch=='#'時循環結束
	{
		if (!IN(ch,operate))                // 判斷ch 是否屬于操作符集合operate,
		{									
			ChangeOPND(p,pos,n,operand);	// 如果不屬于操作符,把其轉成操作數
			p+=(n-1);						// 移動字符串指針	
			CrtNode( t,pos++, S_BiT);         // 建葉子結點
		
		}
		else 
		{
			switch (ch)                     // 如果屬于操作符 
			{
			case '(' : e.OPTR = ch;
					   Push(S_OPTR, e);     // 左括號先進棧
					   break;
			case ')' : {					// 脫括號創建子樹
							Pop(S_OPTR, c);	
							while (c.OPTR!= '(' )
							{ 
								CrtSubtree( t, c.OPTR,S_BiT);
								Pop(S_OPTR, c);
							}
							break; 
					   }
			default :   {
							while(GetTop(S_OPTR, c) && (precede(c.OPTR,ch))) // 棧頂元素優先權高
							{ 
								CrtSubtree( t, c.OPTR, S_BiT);               // 建子樹.
								Pop(S_OPTR, c);                          
							}
							if (ch!= '#')   
							{
								e.OPTR = ch;
								Push( S_OPTR, e);			// 如果ch不為#,讓ch進棧
							}
							break;
						} // default
			} // switch
		} // else
		if ( ch!= '#' ) { p++;  ch = *p;}					// 如果ch不為#,p指針后移
		GetTop(S_OPTR,e);
	} // while
	e.BiT = t;
	Pop(S_BiT, e);
} // CrtExptree

OElemType Value(BiTree T, OElemType *operand)
{
	// 遞歸求值,使用后序遍歷,operand數組存放葉子結點的數值
	OElemType lv,rv,v;
	if (!T) return 0;
	if (!T->lchild && !T->rchild)    return operand[T->data]; 
	lv = Value(T->lchild,operand);
	rv = Value(T->rchild,operand);
	switch (T->data)
	{
	case PLUS:  v = lv+rv; 
				break;
	case MINUS: v = lv-rv; 
				break;
	case ASTERISK: v = lv*rv; 
					break;
	case SLANT: if (rv==0)  ERRORMESSAGE("ERROR");  // 除法運算分母不能為零
				v = lv/rv; 
				break;
	}
	return v;
}//Value