e3888_57_0.cpp

二叉树实现算术表达式存储。前序输入表达式

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef enum {ERROR,OK} Status;
typedef struct
{
	char c;
	float f;
}TElemType;
typedef struct BiTNode
{
	TElemType data;
	struct BiTNode *lchild,*rchild,*parent;
}BiTNode,*BiTree;

BiTree pre=NULL;

Status ReadExpr(BiTree &T)
{
	TElemType ch;
	scanf("%c",&ch.c);
	if(ch.c>='0'&&ch.c<='9'||ch.c>='a'&&ch.c<='z') 
	{
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
		return ERROR;
		T->data.c=ch.c;
		T->data.f=0;
		T->parent=pre;
		T->lchild=NULL;
		T->rchild=NULL;
	}
	else if(ch.c=='+'||ch.c=='-'||ch.c=='*'||ch.c=='/'||ch.c=='^')
	{	
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) return ERROR;
		T->data.c=ch.c;
		T->data.f=0;
		T->parent=pre;
		pre=T;
		ReadExpr(T->lchild);
		ReadExpr(T->rchild);
		pre=pre->parent;
	}
	else 
	{
		printf("输入不合法!\n");
		return ERROR;
	}
	return OK;
}

char Precede(char opa,char opb)
{
	if(opb=='+'||opb=='-')
		return '>';
	else if(opa=='+'||opa=='-')
		return '<';
	else if(opb=='*'||opb=='/')
		return '>';
	else if(opa=='*'||opa=='/')
		return '<';
	else
		return '>';
}

Status WriteExpr(BiTree T)
{
	if(T!=NULL)
	{
		if(WriteExpr(T->lchild))
		{
			if(T->parent!=NULL&&T->parent->parent!=NULL)
			   if(Precede(T->parent->data.c,T->parent->parent->data.c)=='<') 
				   if(T==T->parent->lchild)
						printf("(");
			printf("%c",T->data);
		}
		if(WriteExpr(T->rchild))
		{
			if(T->parent!=NULL&&T->parent->parent!=NULL)
				if(Precede(T->parent->data.c,T->parent->parent->data.c)=='<') 
					if(T==T->parent->rchild)
						printf(")");
			return OK;
		}
		return ERROR;
	}
	else return OK;
}

Status Assign(BiTree &T,char c,float i)
{
	if(T!=NULL)
	{
		if(Assign(T->lchild,c,i))
		{
			if(T->data.c==c)
				T->data.f=i;
			else if(T->data.c>='0'&&T->data.c<='9')
				T->data.f=(float)((T->data.c)-48);
		}
		if(Assign(T->rchild,c,i))
		{
			return OK;
		}
		return ERROR;
	}
	else return OK;
}

float Power(float a,int b)
{
	float answer;
	int i;
	answer=1;
	for(i=0;i<b;i++)
		answer*=a;
	return answer;
}

float Compute(float a,char op,float b)
{
	float answer;
	switch(op)
	{
	case '+':answer=a+b;break;
	case '-':answer=a-b;break;
	case '*':answer=a*b;break;
	case '/':if(b==0.0) {printf("Divide by zero!");return 0;}
		     else answer=a/b;
			 break;
    case '^':answer=Power(a,(int)b);break;
	default :printf("operation error!\n");break;
	}
		return answer;
}


float ans=0.0,lans=0.0,rans=0.0;
float Value(BiTree T)
{
	if(T!=NULL)
	{
		if(T->lchild!=NULL)
			lans=Value(T->lchild);
		if(T->rchild!=NULL)
			rans=Value(T->rchild);
		if(T->lchild==NULL&&T->parent->lchild==T)
		{
			lans=T->data.f;
			return lans;
		}
		else if(T->rchild==NULL&&T->parent->rchild==T)
		{
			rans=T->data.f;
			return rans;
		}
		else 
		{
			ans=Compute(lans,T->data.c,rans);
			return ans;
		}
	}
	else return ans;
}

BiTree CompoundExpr(char c,BiTree E1,BiTree E2)
{
	BiTree T;
	if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) return NULL;
	T->data.c=c;
	T->lchild=E1;
	T->rchild=E2;
	T->parent=NULL;
	E1->parent=T;
	E2->parent=T;
	return T;
}


Status main()
{	
	BiTree T=NULL,T1=NULL,T2=NULL,T3=NULL;
	float f,answer=0.0;
	char c='x';
	while(1)
	{
		printf("*************************\n");
		printf("1.前序输入表达式.\n");
		printf("2.输出表达式.\n");
		printf("3.变量赋值.\n");
		printf("4.计算表达式值.\n");
		printf("5.合并表达式.\n");
		printf("6.退出.\n");
		printf("%%");
		fflush(stdin);
		scanf("%c",&c);
		fflush(stdin);
		switch(c)
		{
		case '1':printf("输入表达式\n");ReadExpr(T);break;
		case '2':WriteExpr(T);printf("\n");break;
		case '3':printf("输入赋值变量:");scanf("%c",&c);
			     printf("输入变量值:");scanf("%f",&f);
				 Assign(T,c,f);
				 break;
		case '4':answer=Value(T);printf("结果是:%f\n",answer);break;
		case '5':printf("输入表达式A:\n");
			     ReadExpr(T1);
				 fflush(stdin);
				 printf("输入表达式B:\n");
				 ReadExpr(T2);
				 fflush(stdin);
				 printf("输入合并符号:\n");
				 scanf("%c",&c);
				 printf("合并后表达式为:\n");
				 T3=CompoundExpr(c,T1,T2);
				 WriteExpr(T3);
				 printf("\n");
				 break;
		case '6':return OK;
		default:printf("输入错误!\n");break;
		}
	}
    return OK;
}