表达式类型的实现.cpp

用二叉树表示的表达式,用先序输入,显示表达式时.有括号先示优先关系,同时对表达式的变量赋值时求表达式的值

/*
本程序是用二叉树来存储一个表达式Expression,而表达式Expression内只含有变量(a~z),常量(0~9)和二元运算
符(+,-,*,/,^(乘幂)).程序由用户以字符形式按先序序列输入表达式,如果只输入一个表达式,则可对算术表达式
求值;否则则求出的是复合的表达式.
 */
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedef char TelemType;
typedef struct BiTNode{//二叉树的结构
	TelemType	data;
	struct BiTNode	*lchild,*rchild;
}BiTNode,*BiTree;

int Op(char ch){//判断ch是为运算数还是运算符,否则返回-1表示出错.
	if((ch>='A' && ch<='Z') || (ch>='a' && ch<='z') || (ch>='0' && ch<='9'))
		return 1;
	else if(ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^') 
		return 0;
	else	return -1;
}

int Precede(char c1,char c2){//判断运算符优先级操作,优先级高返回1,优先级低返回0
	if(c1=='^' && c1!='^')
		return 1;
	if(c1=='*' && (c2!='^' && c2!='*'))
		return 1;
	if(c1=='/' && (c2!='^' && c2!='*' && c2!='/'))
		return 1;
	return 0;
}

int Operate(int x,int y,char ch){//运算操作:x(ch)y
	int i,count;
	if(ch=='+')			return(x+y);
	else if(ch=='-')	return(x-y);
	else if(ch=='*')	return(x*y);
	else if(ch=='/')	return(x/y);
	else if(ch=='^'){
		count=1;
		for(i=1;i<=y;i++)
			count=x*count;
		return count;
	}
	else{
		printf("运算符错误\n");
		exit(0);
	}
}

int	flag,letter;//用flag来指示输入表达式中的某个字符是否为运算数,是则置1,否则为0.
char chars;
void ReadExpr(BiTree &T){//先序建立二叉树
	char ch;
	if(flag)	T=NULL;//flag=1,接收的字符为运算数,则不需做递归,直接返回.
	else{
		ch=getchar();
/*		if(Op(ch)){
			letter++;
			chars=ch;
			if(chars!=ch)	letter++;
		}*/
		if(!(T=(BiTree)malloc(sizeof(BiTNode)))){
			printf("malloc error!\n");
			exit(0);
		}
		if(Op(ch)==-1){
			printf("输入错误!\n");
			exit(0);
		}
		if(ch>='0' && ch<='9')//识别运算数,并把字符形式转化成整数形式
			ch=ch-48;
		else if(Op(ch)){
			if(chars!=ch)
				letter++;//letter来指示表达式中变量的个数
			chars=ch;
		}
		T->data=ch;
		if(Op(ch))//ch为运算数
			flag=1;
		ReadExpr(T->lchild);
		if(!Op(ch))//ch为运算符
			flag=0;
		ReadExpr(T->rchild);
	}
	return;
}

void WriteExpr(BiTree &T){//中序遍历二叉树,并在适当的地方加括号,保持运算顺序
	int flag1=0,flag2=0;
	if(T){
		if(T->lchild && !Op(T->lchild->data)){
			if(Precede(T->data,T->lchild->data)){//父母的优先级比它左孩子的优先级高
					printf("(");				//则打印左括号,同时用flag1来指示左孩子中
					flag1=1;					//已经有左括号了,需要加右括号
				}
		}
		WriteExpr(T->lchild);
		if(flag1)	printf(")");//加右括号
		if(T->data>=0 && T->data<=9)	printf("%c",T->data+48);//用字符形式输出
		else		printf("%c",T->data);
		if(T->rchild && !Op(T->rchild->data)){	//父母的优先级比它右孩子的优先级高
			if(Precede(T->data,T->rchild->data)){//则打印左括号,同时用flag2来指示左孩子中
					printf("(");				//已经有左括号了,需要加右括号
					flag2=1;
			}
		}
		WriteExpr(T->rchild);//打印右括号
		if(flag2)	printf(")");
	}
	return ;
}

void Assign(BiTree &T,TelemType V,int c){//对变量V赋值(V=c).变量的初值为0
	//按先序遍历整棵二叉树
	if(T){
		if(T->data==V)
			T->data=(char)c;
		if(T->lchild)
			Assign(T->lchild,V,c);
		if(T->rchild)
			Assign(T->rchild,V,c);
	}
}

void Value(BiTree &T){//对表达式进行求值,按中序遍历整棵二叉树
	char optr;
	if(T){
		if(T->lchild)
			Value(T->lchild);
		if(T->rchild)
			Value(T->rchild);
		if(!Op(T->data)){//T->data为运算符,则到出它的左右孩子进行运算
			optr=T->data;
			T->data=(char)Operate(T->lchild->data,T->rchild->data,optr);
		}
	}
	return;
}
BiTree CompoundExpr(char P,BiTree E1,BiTree E2){//表达式复合(E1)P(E2)
	BiTree q;
	if((q=(BiTree)malloc(sizeof(BiTNode)))==NULL){
		printf("malloc error!\n");
		exit(0);
	}
	q->data=P;
	q->lchild=E1;
	q->rchild=E2;
	return q;
}
void DestoryTree(BiTree &T){//树的删除操作,按后根遍历整棵二叉树.
	if(T){
		if(T->lchild)
			DestoryTree(T->lchild);
		if(T->rchild)
			DestoryTree(T->rchild);
		free(T);
	}
	return ;
}

void main(){
	BiTree E1,E2,p;
	int temp;
	char ch,c;
	do{
		fflush(stdin);
		printf("请按先序输入表达式:");
		ReadExpr(E1);
		fflush(stdin);
		printf("表达式为:");
		WriteExpr(E1);
		printf("\n是否继续输入表达式?[y/n]");
		c=getchar();
		if(c=='y' || c=='Y'){
			printf("\n请按先序输入表达式:");
			flag=0;letter=0;
			fflush(stdin);
			ReadExpr(E2);
			printf("表达式为:");
			WriteExpr(E2);
			fflush(stdin);
			printf("\n请输入复合的运算符:");
			c=getchar();
			p=CompoundExpr(c,E1,E2);
			printf("新的复合表达式为:");
			WriteExpr(p);
			printf("\n");
			DestoryTree(p);
		}
		else{
			if(letter){
				while(letter){//对求知数进行赋值
					printf("请输入要赋值的操作数和所赋的值(空格隔开):");
					fflush(stdin);
					scanf("%c %d",&ch,&temp);
					Assign(E1,ch,temp);
					letter--;
				}
				printf("赋值后的表达式为:");
				WriteExpr(E1);
				printf("\n运算结果为:");
				WriteExpr(E1);
				Value(E1);
				printf("=%d\n",(int)E1->data);
			}
			else{
				printf("运算结果为:");
				WriteExpr(E1);
				Value(E1);
				printf("=%d\n",(int)E1->data);
			}
			DestoryTree(E1);
		}
		letter=0;flag=0;chars=' ';
		fflush(stdin);
		printf("是否继续?[y/n]");
		c=getchar();
	}while(c=='y' || c=='Y');
}