由数字式子生成对应的二叉树

/*由式子生成二叉树*/
//例如输入：1-2*3+4/(5+6)-7*8#
#include<stdio.h>
#include<malloc.h>
//////////////////////////////////////////////////////////////////////////////////////////////////
//定义数据结构
#define MaxSize 50
typedef struct{
	int b;//指示是数字还是运算符，如果是数字为0，如果是运算符，也用来区分是同类中是第几个运算
	int pri;
	int data;
}Array;
typedef struct BitNode{
	//ElemType data;
	Array data;
	struct BitNode *lchild,*rchild;
}BitNode,*BiTree;
//////////////////////////////////////////////////////////////////////////////////////////////////
void Print(Array A[],int length){
	int i=0;
	while(i<length){
		if(A[i].b)
			printf("%c",A[i].data);
		else printf("%d",A[i].data);
		i++;
	}
	printf("\n");
}
int ToInOrder(Array A[],Array B[],int length){
	//将式子转化为中序，即效果上是去除括号
	int i=0,k=0;
	for(i=0;i<length;i++)
		if(A[i].data!='(' && A[i].data!=')')
			B[k++]=A[i];
	return k;
}
int ToPostOrder(Array A[],Array C[],int length){
	int i=0,k=0;
	Array D[MaxSize];//栈
	int top=-1,temp;
	for(i=0;i<length;i++){
		if(A[i].b!=0){//判断是否是运算符
			temp=A[i].pri;
			if(top!=-1){
				while(top!=-1 && D[top].pri>temp)
					C[k++]=D[top--];//出栈
				if(top!=-1 && D[top].pri==temp){
					top--;//出栈‘（’并且舍弃‘）’
					continue;
				}
			}
			D[++top]=A[i];//入栈
			switch(A[i].data){//修改栈内优先级
			case '+':D[top].pri=3;break;
			case '-':D[top].pri=3;break;
			case '*':D[top].pri=5;break;
			case '/':D[top].pri=5;break;
			case '(':D[top].pri=1;break;
			case ')':D[top].pri=6;break;
			}
		}
		else
			C[k++]=A[i];//如果是数字，直接输出
	}
	while(top!=-1)//出栈
		C[k++]=D[top--];
	return k;
}
BiTree PostInCreateTree(Array A[],Array B[],int l1,int h1,int l2,int h2){//由中序和后序来构造树,l1,h1为最小下标和最大下标
	int i=0,llen=0,rlen=0;
	BiTree T=(BiTree)malloc(sizeof(BitNode));
	T->data=A[h1];//A为后序
	for(i=l2;i<h2;i++)
		if(B[i].data==A[h1].data && B[i].b==A[h1].b)
			break;//B为中序
	if(i<h2){
		llen=i-l2;
		rlen=h2-i;
	}
	if(llen)
		T->lchild=PostInCreateTree(A,B,l1,l1+llen-1,l2,l2+llen-1);
	else
		T->lchild=NULL;
	if(rlen)
		T->rchild=PostInCreateTree(A,B,h1-rlen,h1-1,h2-rlen+1,h2);
	else
		T->rchild=NULL;
	return T;
}
void InOrder(BiTree T){//中序遍历，验证生成的树是否正确
	if(T){
		InOrder(T->lchild);
		if(T->data.b==0)
			printf("%d",T->data.data);
		else
			printf("%c",T->data.data);
		InOrder(T->rchild);
	}
}
int Calculate(BiTree T){//利用树的遍历来求解
	int l=0,r=0;
	if(T){
		l=Calculate(T->lchild);
		r=Calculate(T->rchild);
		if(T->data.b!=0)
			switch(T->data.data){
			case '+':return l+r;
			case '-':return l-r;
			case '*':return l*r;
			case '/':return l/r;
			default : break;
		}
		else return T->data.data;
	}
}
int Calculate2(Array A[],int length){//利用后序序列求解
	Array D[MaxSize];//栈
	int top=-1,i=0;
	for(i=0;i<length;i++)
		if(A[i].b==0)
			D[++top]=A[i];
		else
			switch(A[i].data){
			case '+':D[top-1].data=D[top-1].data+D[top].data;top--;break;
			case '-':D[top-1].data=D[top-1].data-D[top].data;top--;break;
			case '*':D[top-1].data=D[top-1].data*D[top].data;top--;break;
			case '/':D[top-1].data=D[top-1].data/D[top].data;top--;break;
			default : break;
		}
	return D[top].data;
}
//主函数
void main(){
	//输入并处理；
	char ch=0;
	int temp,index=0,q1=1,q2=1,q3=1,q4=1,q5=1,q6=1;
	int lenB=0,lenC=0,result=0,result2=0;
	Array A[MaxSize],B[MaxSize],C[MaxSize];
	BiTree T;
	while(1){
		scanf("%c",&ch);
		if(ch>=48 && ch<=57){//连续输入数字成多位数
			temp=ch-48;
			while(1){
				scanf("%c",&ch);
				if(ch>=48 && ch<=57)
					temp=temp*10+ch-48;
				else break;
			}
			A[index].data=temp;
			A[index].b=0;//指示数字
			index++;
		}
		switch(ch){
		case '+':A[index].data=ch;A[index].b=q1++;A[index].pri=2;index++;break;
		case '-':A[index].data=ch;A[index].b=q2++;A[index].pri=2;index++;break;
		case '*':A[index].data=ch;A[index].b=q3++;A[index].pri=4;index++;break;
		case '/':A[index].data=ch;A[index].b=q4++;A[index].pri=4;index++;break;
		case '(':A[index].data=ch;A[index].b=q5++;A[index].pri=6;index++;break;
		case ')':A[index].data=ch;A[index].b=q6++;A[index].pri=1;index++;break;
		default :break;
		}
		if(ch=='#') break;
	}
	//Print(A,index);
	lenB=ToInOrder(A,B,index);//转为树的中序
	//Print(B,lenB);
	lenC=ToPostOrder(A,C,index);//转为树的后序
	//Print(C,lenC);
	T=PostInCreateTree(C,B,0,lenC-1,0,lenB-1);//生成二叉树
	InOrder(T);
	result=Calculate(T);
	printf("\n%d\n",result);
	result2=Calculate2(C,lenC);
	printf("%d\n",result2);
}

由数字式子生成对应的二叉树

原文：http://blog.csdn.net/o1101574955/article/details/41626161