expbintree.h

数据结构实验练习--计时器

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