expressionmain.cpp

题目：表达式类型的实现 用树来实现前缀算术表达式到正常表达式的转换

#include<stdio.h>
#include<stdlib.h>

typedef struct TNode{
int data;
struct TNode *lchild,*rchild;
}TNode,BiTree;//结点类型，无论是字符、常量还是符号都存放它的ASC||值

typedef struct{
int re;
int value;
}q;//定义辅助结构体存放变量的值

typedef struct{
q Va[50];
int len;
}ht;


char ch; TNode *pl,*pr;//Readexpr函数中的全局变量


int Judge(int c1){
//判断为运算符、变量还是常量
if(c1==42||c1==43||c1==45||c1==47) return 1;
else if(c1==94) return 2;
else if(c1>=48&&c1<=57) return 3;
else if(c1>=97&&c1<=122) return 4;
}//Judge


void Put(ht &H,char c1){
//将变量存入辅助数组
int i;
for(i=0;i<=H.len-1;i++)
  if(c1==H.Va[i].re)break;
if(i>H.len-1){
   H.Va[H.len].re=c1;
   H.len++;
}//if
}//Put 


void ReadExpr(BiTree &T,ht &H){
//创建树，如果是变量，存放入辅助数组
ch=getchar();
T.data=ch;
if(Judge(ch)==1||Judge(ch)==2){
//ch为运算符
	pl=(TNode*)malloc(sizeof(TNode));
	T.lchild=pl;
    ReadExpr(*(T.lchild),H);
    pr=(TNode*)malloc(sizeof(TNode));
	T.rchild=pr;
	ReadExpr(*(T.rchild),H); 
}//if
else {
//ch为变量或者常量
	if(Judge(ch)==4)Put(H,ch);
	T.lchild=T.rchild=NULL;
}//else
}//ReadExpr


void Assign(ht &H){
//对变量赋值
int i,j,k;
char c1;
printf("How many variable to assingn:");
scanf("%d",&j);
printf("Please input the variable and its value you want to give as:->a=5\n");
for(;j>0;j--){
   fflush(stdin);
   scanf("%c=%d",&c1,&k);
   for(i=0;i<=H.len-1;i++)
   if(c1==H.Va[i].re)
	  H.Va[i].value=k;
}//for
}//Assign


int Change(int a,ht &H){
//将ASC||值转换为数值
int i,r;
if(Judge(a)==3) r=a-48;
else if(Judge(a)==4){
       for(i=0;i<=H.len-1;i++)
		   if(a==H.Va[i].re){
			   r=H.Va[i].value;
			   break;}
}//else if
return r;
}//Change


int Operate(int a1,int theta,int b1){
int io,result;
switch(theta){
      case 42:result=a1*b1;break;
      case 43:result=a1+b1;break;
      case 45:result=a1-b1;break;
      case 47:result=a1/b1;break;
      case 94:for(io=1,result=1;io<=b1;io++) 
              result*=a1;
		      break;
}//switch
return result;
}//Operate


int Value(BiTree *p3,ht &H){
int c,d;
if(p3->rchild==NULL)return Change(p3->data,H);
else{
	c=Value(p3->lchild,H);
	d=Value(p3->rchild,H);
	return Operate(c,p3->data,d);
}//else
}//Value


int Value2(BiTree &T,ht &H){
//计算表达式的值，后序遍历
BiTree *p;
p=&T;
return Value(p,H);
}//Value2


int compare(int n,int m){
//如果n的优先级比m的高，返回1；如果优先级相同，返回2；否则返回0
if(Judge(n)==2&&Judge(m)==1) return 1;
else if((n==47||n==42)&&(m==43||m==45)) return 1;
else if((n==47&&m==42)||(n==42&&m==47)||(n==43&&m==45)||(n==45&&m==43))return 2;
else return 0;
}//compare


void WriteExpr(BiTree &T){
//在写出子树的过程中，要判断算符的优先级，以加括号。
//左子树和右子树的情况略有不同。
int t1,t2,t3;
t1=T.data;
t2=T.lchild->data;
t3=T.rchild->data;
if((Judge(t1)==1||Judge(t1)==2)&&(Judge(t2)==1||Judge(t2)==2)){
  //t1和t2均为运算符
	 if(compare(t1,t2)==1){
     //上一层优先级要高
        printf("(");
		WriteExpr(*(T.lchild));
		printf(")");
		printf("%c",char(t1));
	 }//if
	 else {WriteExpr(*(T.lchild));
	       printf("%c",char(t1));
	 }//else
}//if
else if(Judge(t2)==3||Judge(t2)==4){
  //t2为常量或变量
	printf("%c",char(t2));
	printf("%c",char(t1));  
}//else if
//写出左子树
if((Judge(t1)==1||Judge(t1)==2)&&(Judge(t3)==1||Judge(t3)==2)){
  //t1和t3均为运算符
	 if(compare(t1,t3)==1||compare(t1,t3)==2){
     //上一层优先级要高
        printf("(");
		WriteExpr(*(T.rchild));
		printf(")");
	 }//if
	 else {WriteExpr(*(T.rchild));
	 }//else
}//if
else if(Judge(t3)==3||Judge(t3)==4){
  //t3为常量或变量
	    printf("%c",char(t3));
}//else if
//写出右子树
}//WriteExpr

void WriteExpr1(BiTree &T){
//中序遍历写出表达式，并加适当括号
if(T.rchild==NULL)printf("%c",char(T.data));
else WriteExpr(T);
}//WriteExpr1


void CompoundExpr(BiTree &T,BiTree &T2,BiTree &T3,ht &H1,ht &H2,ht &H3){
//合成表达式，构成新树T3
char c1;
int i,j;
fflush(stdin);
printf("Please input the functor:");
scanf("%c",&c1);
T3.data=c1;
T3.lchild=&T;
T3.rchild=&T2;
for(j=0;j<H2.len;j++){
    for(i=0;i<H1.len;i++){
	   if(H1.Va[i].re==H2.Va[j].re) break;
	}//for
	if(i=H2.len){
	   H1.Va[H1.len].re=H2.Va[j].re;
	   H1.len++;
	}//if
}//for

for(i=0;i<H1.len;i++){
H3.Va[i].re=H1.Va[i].re;
}
H3.len=H1.len;
}//CompoundExpr


void main(){
BiTree T,T2,T3;
int t,i,j;
ht H1,H2,H3;//定义辅助结构体数组存放变量的值

for(t=0;t<50;t++){
  H1.Va[t].re=H1.Va[t].value=0;
  H2.Va[t].re=H2.Va[t].value=0;
  H3.Va[t].re=H3.Va[t].value=0;
}//for
H1.len=H2.len=H3.len=0;
do{
	printf("\n");
	printf("1.ReadExpr(E)\n2.WriteExpr(E)\n3.Assign(V,c)\n4.Value(E)\n5.CompoundExpr(P,E1,E2)\n6.quit\n");
	printf("Please choose 1~6!\n");
	scanf("%d",&i);
	fflush(stdin);
	if(i>6||i<1){
	   printf("Please choose 1~6!\n");
	   continue;
	}//if
	if(i==6)break;
	switch(i){
	   case 1:printf("Please input the expression in preorder.\n");
		      ReadExpr(T,H1);
			  break;
	   case 2:printf("Which expression do you want to write:1 or 3?\n");
		      scanf("%d",&j);
			  printf("The expression is:\n");
			  if(j==1) WriteExpr1(T);
			  else WriteExpr1(T3);
			  break;
	   case 3:printf("Which expression do you want to assign:1 or 3?\n");
		      scanf("%d",&j);
			  fflush(stdin);
              if(j==1)Assign(H1);
			  else Assign(H3);
			  break;
	   case 4:printf("Which expression do you want to value:1 or 3?\n");
		      scanf("%d",&j);
              if(j==1) printf("The result is %d",Value2(T,H1));
			  else printf("The result is %d",Value2(T3,H3));
		      break;
	   case 5:printf("Please input another expression in preorder.\n");
		      ReadExpr(T2,H2);
			  CompoundExpr(T,T2,T3,H1,H2,H3);
		      break;
	   case 6:break;
	}//switch
}while(i>=1&&i<=5);
}//main