5-1.cpp

1.一个表达式和一棵二叉树之间,存在着自然的对应关系.可写一个程序实现基于二叉树表示的算术表达式Expression的操作.

#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef bool status;
typedef struct operand{
	char c;
	int  m;
}operand;

typedef struct bitnode{
    operand data;
	struct bitnode *lchild,*rchild;                 //左右孩子指针
}bitnode,*bitree;



bitree createbitree(bitree &T){
	//按先序次序输入二叉树中的结点（一个字符），空格字符表示空树，构造二叉链表表示的二叉树
	char  c;
	operand p;
	int i;
	fflush(stdin);
	scanf("%c",&c);
	if(c==' ')
		T=NULL;
	else{
		if(!(T=(bitnode *)malloc(sizeof(bitnode))))
	    		return NULL;
		
		if(c>='0'&&c<='9'){
		     c=c-48;
             p.m=int(c);
			 T->data=p;
		}
		else{
		p.c=c;                                      //生成根结点
		T->data=p;
		}
		if(c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!='^'){
			T->lchild=NULL;

			T->rchild=NULL;
		}
	
		createbitree(T->lchild);                    //构造左子树
		createbitree(T->rchild);                    //构造右子树
	}
	return  T;
}
  




void inorder(bitree T){                    //中序遍历二叉树打印结点内容
	operand p;
	if(T!=NULL){
		inorder(T->lchild);         //处理左子树 
		p=T->data;
		if(((p.m))>=0&&((p.m)<=9)) //打印结点
			printf("%d",p.m);
		else
			printf("%c",p.c);
		inorder(T->rchild);                //处理右子树
	}
}



int chengmi(char oper,int oper1,int oper2){              //计算乘幂
	if(oper2==1)
		return oper1;
	else
		return oper1*chengmi(oper,oper1,oper2-1);
}




int get_value(char oper,int oper1,int oper2){             //抽取运算值并计算
	int z;
	switch((char) oper){
	case '*':
		return z=(oper1*oper2);
		break;
    case '/':
		return z=(oper1/oper2);
		break;
    case '+':
		return z=(oper1+oper2);
		break;
    case '-':
		return z=(oper1-oper2);
		break;
	case '^':
		z=chengmi('^',oper1,oper2);
		return z;
		break;
 
	}
}



status postorder(bitree &T){   //	后序遍历二叉树并对表达式中的变量赋值

	int k;
	char n,a[10],b[10] ;
	operand p;
	if(T!=NULL){
		postorder(T->lchild);            //处理左子树
		postorder(T->rchild);           //处理右子树
    static int i=0;
		p=T->data;
	if(p.c>='a'&&p.c<='z'){
		a[i]=p.c;
		for(k=0;k-1<i-1;k++)
			if(a[i]==a[k]){
				a[i]=b[k];
				break;
			}
		if(k-1==i-1){
			a[i-1]=p.c;
			printf("\n请输入变量的值%c=：",p.c);
			fflush(stdin);
			scanf("%c",&n);
			b[i-1]=n;
		//	a[i]=b[i];
			
			p.m=int(b[i-1]-48);
            T->data=p;
			i++;
		
			
		}
	}
	}
	return true;
}


int calculate(bitree T){                  //计算表达式的值
	int oper1=0,oper2=0,z;                 //前后两个操作数
	operand p;
	postorder(T);
	if(T->lchild==NULL&&T->rchild==NULL){
		p=T->data;
		return z=(p.m)-0;
	}
	else{
		oper1=calculate(T->lchild);        //左子树
		oper2=calculate(T->rchild);     //右子树
		p=T->data;
	z=get_value((p.c),oper1,oper2);
	return z;
	}
}



void main(){
	int cal_result;                      //计算结果
	bitree T,root;
	printf("请按先序顺序输入二叉树的结点，若孩子为空,即结点元素不是运算符，请输入两个空格\n");
    root=createbitree(T);
	printf("\ninorder expression:\n");   //打印中序表达式
	inorder(root);
	printf("\n*******************************************************************************");
	printf("\n如果同一个变量出现多次，请对同一个变量输入相同的值\n");
	cal_result=calculate(root);            //计算表达式的值
	printf("\ncaluate result is %d \n",cal_result);
}