bitree.cpp

表达式和二叉树之间存在对应关系

// BiTree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#define LETT e=='+'||e=='-'||e=='*'||e=='/'||e=='~'
#define LETT1 e1=='+'||e1=='-'||e1=='*'||e1=='/'||e1=='~' 

typedef struct BiTNode{//define type of the node of the tree
	char data;
	int flag;  //标志是否加括号
	char size; //标志左或右（叶子）结点
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

struct vail{  //暂时存放字母
	char v;
	int value;
}va[20];
int count=0;//计算变量个数
char e,e1;    //全局字符变量
BiTree q;  


void main(){

	void ReadExpr(BiTree &p); //建立二叉树
	int Precede1(char x,char y);  //比较算符优先次序
	int Precede2(char x,char y); 
	void Flag(BiTree &p);   //标志需要加括号的叶子结点
	void WriteExpr(BiTree p);  //输出中序表达式
	void Assign(char v,int c); //赋值
	int Operate(char f,int m,int n); //计算每棵子树的结果
	int Value(BiTree p); //计算整个表达式的结果
	void CompoundExpr(char p,BiTree p1,BiTree p2); //将两个表达式合在一起
	
	
	BiTree p0,p1,p2; //指向树根
	char c1,p; 
	int i,k,v,c,result;

    do{
		printf("1.Calculate the expression.\n");
		printf("2.CompoundExpr.\n");
		printf("3.exit.\n");
		printf("\n");
		printf("input the number you choose:\n");
		scanf("%d",&k);
		switch(k){
		    case 1:{
				    printf("Please input the expression(前缀形式):\n");
					fflush(stdin); 
				    p0=NULL;
				    ReadExpr(p0);  //构造二叉树
				    printf("The ReadExpr had does.\n");
                    printf("\n");

				    printf("Now print the expression inorder:\n");
					Flag(p0);
                    WriteExpr(p0);//以中序输出二叉树
					putchar('\n');

                    printf("set value of vailable.\n"); //变量赋值
			     	for(i=0;i<count;i++) //赋初值为0
					     va[i].value=0;
				    while(1){
					     printf("input the vailable you want to set value(end by 0):\n");
					     fflush(stdin);
					     scanf("%c",&v);
					     printf("input the new value(end by 0):\n");
					     scanf("%d",&c);
					     if(v!=48&&c!=0)  Assign(v,c);
					    else break;
					}

				    printf("Calculate result of the expression\n");
				    result=Value(p0);  
				    printf("The result is %d\n",result);
				   }
				   break;
			case 2:{
				    printf("Please create the 1st expression:\n");
                    fflush(stdin); 
				    p1=NULL;
				    ReadExpr(p1);
				    printf("Please create the 2nd expression:\n");
					fflush(stdin); 
				    p2=NULL;
				    ReadExpr(p2);
			  	    printf("input the operation:\n");
				    fflush(stdin);
				    scanf("%c",&p);
			 	    printf("create a complex expression.\n");
				    CompoundExpr(p,p1,p2);
					printf("\n");
				   }
				break;
			case 3:
				   return ;
            default:{
				     printf("The number you choose is unsuiable.\n");
				     printf("Please choose the right number.\n");
					}
		}//switch
		printf("Do you want to continue(y OR n):\n");
		fflush(stdin);
		c1=getchar();
	}while(c1=='y');
}


//*****************************************************************
//Operate.cpp--计算子树的值
int Operate(char f,int m,int n){
    int t=1;

	switch(f){
	      case '+' :
			  return m+n;
			  break;
          case '-' :
			  return m-n;
			  break;
          case '*' :
			  return m*n;
			  break;
		  case '/' :
			  if(n==0){
				  printf("The divider is 0,error!\n");
				  exit(0);
			  }
			  return m/n;
			  break;
          case '~' :
			  while(n!=0){
				  t=t*m;
				  n--;
			  }
			  return t;
			  break;
          default:
			  printf("Error!\n");
			  exit(0);
	}
}


//-------------------------------------------------------
int Precede1(char x,char y){ //算符优先级比较(左子树)
	int z;
	if(x=='+'||x=='-'){ //+或-
		switch(y){
		   case '+': z=0;break;
           case '-': z=0;break;
		   case '*': z=0;break;
           case '/': z=0;break;
           case '~': z=0;break;
		}
	}
	if(x=='*'||x=='/'){
		switch(y){
		   case '+': z=1;break;
           case '-': z=1;break;
		   case '*': z=0;break;
           case '/': z=0;break;
           case '~': z=0;break;
		}
	}
	if(x=='~'){
		switch(y){
           case '+': z=1;break;
           case '-': z=1;break;
		   case '*': z=1;break;
           case '/': z=1;break;
           case '~': z=0;break;
		}
	}
    return z;
}



int Precede2(char x,char y){ //算符优先级比较(右子树)
	int z;
	if(x=='+'||x=='-'){ //+或-
		switch(y){
		   case '+': z=1;break;
           case '-': z=1;break;
		   case '*': z=0;break;
           case '/': z=0;break;
           case '~': z=0;break;
		}
	}
	if(x=='*'||x=='/'){
		switch(y){
		   case '+': z=1;break;
           case '-': z=1;break;
		   case '*': z=1;break;
           case '/': z=1;break;
           case '~': z=0;break;
		}
	}
	if(x=='~'){
		switch(y){
           case '+': z=1;break;
           case '-': z=1;break;
		   case '*': z=1;break;
           case '/': z=1;break;
           case '~': z=1;break;
		}
	}
    return z;
}

 
//----------------------------------------------------------
//ReadExpr.cpp--建立二叉树
void ReadExpr(BiTree &p){ //先以字符型建立
	e=getchar();
	if(!(e>=48&&e<=57||(LETT)||e>=97&&e<=122)){//输入是否合法
		printf("input error!\n");
		exit(0);
	}
	if(e=='\n')  p=NULL;
	else{
		p=(BiTree)malloc(sizeof(BiTNode));
		p->data=e;
		p->flag=0;   //赋初值
		p->size='l'; //先设为左 
		if(LETT){ //若e为算符
			ReadExpr(p->lchild);
			ReadExpr(p->rchild);
		}
		else{
			p->lchild=NULL;
			p->rchild=NULL;
		} 
	}
}

/*
void Error(BiTree p){//检查是否有错
	e=p->data;
	if(LETT&&(p->lchild==NULL||p->rchild==NULL)){ //e为算符且左右子树至少一为空
		printf("Can't calculate,ERROR!\n");
		exit(0);
	}
	if((e>=48&&e<=57||e>=97&&e<=122)&&(p->lchild!=NULL||p->rchild!=NULL)){ //操作数且左右子树至少一不空
		printf("Can't calculate,ERROR!\n");
		exit(0);
	}
	Error(p->lchild);
	Error(p->rchild);
}
*/ 

//-----------------------------------------------------------------------
//Flag.cpp ----用于加括号  标志需要添加括号的结点
//用两个指针分别指在上下相邻的两个结点，若都为算符，比较
//若子树优先级低，标志需加括号；同时也标志其左右结点
void Flag(BiTree &p){
	if(p==NULL)  return ;
	else{
		q=p->lchild;   //先左子树 q为全局变量
		if(q!=NULL){ //保证q->data'有值'
		   e1=q->data;
		   if(LETT1){ //子树结点为算符   
		     	q->flag=Precede1(p->data,e1); //1时表示子树根优先级小，0表示优先级大
                (q->lchild->flag)+=q->flag;  //左右子树的flag同时改变
                (q->rchild->flag)+=q->flag;
				q->rchild->size='r';  //右子树设为r
		   }
		}
		Flag(p->lchild);

		q=p->rchild;  //后右子树
		if(q!=NULL){
		   e1=q->data;
		   if(LETT1){
	    		while(q->flag!=0){ //于左子树匹配
                   (q->rchild->flag)++;  //若上结点已有标志，为左子树的要求，让右结点标志累加
		    		(q->flag)--;
				}
			    q->flag=Precede2(p->data,e1); //1时表示优先级小
                (q->lchild->flag)+=q->flag;
                (q->rchild->flag)+=q->flag;
				q->rchild->size='r';    //右子树设为r
		   }
		}
		Flag(p->rchild);
	}
}

				
//---------------------------------------------------------------------
//WriteExpr.cpp--中序输出二叉树
void WriteExpr(BiTree p){    
    if(p==NULL)  return ;
	else{
        WriteExpr(p->lchild);
		e=p->data;
        if(e>=97&&e<=122){ //为字符时暂存于va[]
			va[count].v=e;
			count++;
		}

		if(e>=48&&e<=57||e>=97&&e<=122){  //为叶子结点
			while(p->size=='l'&&p->flag!=0){ //有左括号标志
				putchar('(');
				(p->flag)--;
			}
	        printf("%c",e);
			while(p->size=='r'&&p->flag!=0){ //右括号标志
				putchar(')');
				(p->flag)--;
			}
		}
		else printf("%c",e);
		WriteExpr(p->rchild);
	}
}



//-------------------------------------------------------------
//Assign.cpp   
void Assign(char v,int c){//此时在va[]中已将字符存入
	int i=0;
	while(i<count&&va[i].v!=v)
		i++;
	if(va[i].v==v)
		va[i].value=c;
}
          
//-------------------------------------------------------------
//value.cpp
int Value(BiTree p){ //后根计算表达式结果
	int i=0,m,n;

	if(p!=NULL){
	   	m=Value(p->lchild);
		n=Value(p->rchild);
		e=p->data;
		if(LETT){//e为算符,计算子树结果
			return Operate(e,m,n);
		}
		else{//e为字符数字或字母
			if(e>=48&&e<=57)
				return e-48;
			else{//e为字母
				while(e!=va[i].v&&i<count)
					i++;
				if(e==va[i].v)
					return va[i].value;
			}
		}
	}
}



//----------------------------------------------------------------
//CompoundExpr.cpp
void CompoundExpr(char p,BiTree p1,BiTree p2){
	BiTree q0;  //不可用q
	q0=(BiTree)malloc(sizeof(BiTNode));
	q0->lchild=p1;
	q0->rchild=p2;
	q0->data=p;
	Flag(q0);
    WriteExpr(q0);    
}