表达式二叉树代码.docx

该【表达式二叉树代码 】是由【niupai21】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【表达式二叉树代码 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。#include<>
#include<>
#include<>
#include<>
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW0
typedefintStatus;
typedefenum{INT,CHAR}ElemTag;
typedefstructTElemType
{
ElemTagtag;
union
{
intnum;
charc;
};
}TElemType;
typedefstructBiTNode
{
TElemTypedata;structBiTNode*lchild/*rchild;
}BiTNode/BiTree;
typedefBiTreeSEIemType;
typedefcharSEIemTypel;
#defineSTACK」NIT_SIZE10
#defineSTACKINCREMENT2
typedefstructSqStack
{
SEIemType*base;
SEIemType*top;
intstacksize;
}SqStack;
typedefstructSqStackl
{
SEIemTypel*base;
SEIemTypel*top;intstacksize;
}SqStackl;
StatuslnitStack(SqStack*S)
(*S).base=(SEIemType*)malloc(STACKJNIT_SIZE*sizeof(SEIemType));if(!(*S).base)
exit(OVERFLOW);
(*S).top=(*S).base;
(*S).stacksize=S7ACKJNIT_SIZE;
returnOK;
}
StatusStackEmpty(SqStackS)
{
if(==)returnTRUE;
elsereturnFALSE;
}
StatusPush(SqStack*S/SEIemTypee)
{
if((*S).top-(*S).base>=(*S).stacksize)
{
(*S).base=(SEIemType
*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SEIemType));if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;rS).stacksize+二STACKINCREMENT;
}
*((*S).top)++=e;
returnOK;
}
StatusPop(SqStack*S,SEIemType*e)
{
if((*S).top==(*S).base)returnERROR;
*e=*-(*S).top;
returnOK;
}
StatusGetTop(SqStackS’SEIemType*e)
{
if(>)
{
*e=*(-l);
returnOK;
}
else
returnERROR;
}
StatuslnitStackl(SqStackl*S)
(*S).base=(SEIemTypel*)malloc(STACK」NIT_SIZE*sizeof(SEIemTypel));if(!(*S).base)
exit(OVERFLOW);
(*S).top=(*S).base;
仁S)・stacksize二STACK_INIT_SIZE;
returnOK;
}
StatusStackEmptyl(SqStacklS)
{
if(==)returnTRUE;
elsereturnFALSE;
}
StatusPushl(SqStackl*S,SEIemTypele)
{
if((*S).top-(*S).base>=(*S).stacksize)
{
(*S).base=(SEIemTypel
*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SEIemTypel));if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;
rS).stacksize+二STACKINCREMENT;
}
*((*S).top)++=e;
returnOK;
}
StatusPopl(SqStackl*S,SEIemTypel*e)
{
if((*S).top==(*S).base)returnERROR;
*e=*-(*S).top;
returnOK;
}
StatusGetTopl(SqStacklS^EIemTypel*e)
{
if(>)
{
*e=*(-l);
returnOK;
}else
returnERROR;
}
longpower(intx」ntexp)
{
longresult;
inti;
for(i=l,result=l;i<=exp;i++)
result*=x;
returnresult;
}
#”
#include<>
intsave_number[51];
charExpr_String[5O];
Statuslnput_Expr(char*stringjntflag)
{
if(flag==O)printf("\n请输入正确的前缀表示式:");
elseprintff'Xn输入前面前缀表达式对应的带括弧的中缀表示式:“);
flushallf);
gets(string);
if(strlen(string)==l)
if(string[O]==,+,||string[O]==,-,||string[0]==,*,||string[O]==,/,||string[O]==,A,)
{printf("\n表达式只有一个字符,为运算符,错误!”);returnERROR;}else
if((string[0]>=,0,&&string[0]<,9,)11(string[O]>=,a,&&string[O]<=lz,)||(string[0]>=,A,&&string[0]<=,
Z1))
{printff'Xn表达式只有一个字符!”);returnOK;}
else{printf("\n输入的字符不是运算符也不是变量常量,错误!“);returnERROR;}returnOK;
}
voidjudge_value(BiTree*Ezchar*string,inti)
{
if(string[i]>=,0,&&string[i]<=,9,)
{(*E)->=INT;(*E)->=string[i]-48;}
elseif(string[i]>=l&&string[i]<=20)
{(*E)->=INT;(*E)->=save_number[string[i]];}
else
{(*E)->=CHAR;(*E)->=string[i];}
}
StatusReadExpr(BiTree*E,char*exprstring)
SqStackS;
inti,len;
BiTreep,q;
(*E)=(BiTree)malloc(sizeof(BiTNode));
(*E)->lchild=NULL;
(*E)->rchild=NULL;
len二strlen(exprstring);
if(len==l)
judge_value(E,exprstring,O);
else
{
judge_value(E,exprstring,O);
lnitStack(&S);
q=(*E);
Push(&S,q);
Push(&S,q);
for(i=l;i<len&&!StackEmpty(S);i++)
{
p=(BiTree)malloc(sizeof(B订Node));
judge_value(&p,exprstring,i);
p->lchild=NULL;
p->rchild=NULL;
if(exprstring[i]=='+,||exprstring[i]=='-,||exprstring[i]二二‘和||exprstring[i]二二7'|[exprstring[i]二二
{
if(!q->lchild){q->lchild=p;Push(&S,p);q=p;}
else{q->rchild=p;Push(&S,p);q=p;}
}
else
{
if(!q->lchild){q->lchild=p;Pop(&S,&q);}
else{q->rchild=p;Pop(&S,&q);}
}
}
if(StackEmpty(S)&&i>=len) returnOK;
else
{
printf("\n输入的表达式有误!”);
returnERROR;
}
}
voidShowTree(BiTree&E,intt)
inti;
if(E)
{
ShowTree(E->rchild,t+5);
for(i=0;i<t;i++)
{printfC“);}
printf(”%5c\rCE・>);
ShowTree(E->lchild,t+5);
}
}
StatusPri_Compare(charcl^harc2)
{
if((cl==*11 11 Icl=a11cl==7')&&(c2==,A,11c2==*11c2==TIc2==A11c2二
=■/■))
{
if(cl==,A,)
{
if(c2!=,A,)returnOK;
elsereturnERROR;
}
if(cl==,*,||cl==7,)
{
if(c2==,A,)returnERROR;
elsereturnOK;
}
elsereturnERROR;
}
elsereturnERROR;
}
StatusReadjnorder_Expr(char*string,char*pre_expr)
{
intijjen,char_number";
intnumber;
charczcl;
SqStacklS;
lnitStackl(&S);
Pushl(&S;#');
len二strlen(string);
c=string[len-l];
i=len-l;
while(!StackEmptyl(S)&&i>=0)
Popl(&S,&c);
whilelch1)')
{
*pre_expr++=c;
if(!StackEmptyl(S)&&GetTopl(S,&cl)&&clh1#')Popl(&S,&c);else{printf("\n输入的表达式有误!");returnERROR;}
}
}
elseif(c==T)
{
Pushl(&S,c);
}
elseif(c>=,Ol&&c<-91)
{
number=c-48;
for(cl=string[i-l]j=l;(cl>=,0,&&cl<=l9,)&&i>=0;j++/i-)
{
number=(cl-48)*power(10J)+number;cl=string[i-2j;
}
save_number[char_number]二number;*pre_expr++=char_number++;}
elseif((c>=Q&&cc=h)||(c>=7V&&c<='Z'))
if((string[i-l]>=,Ol&&string[i-l]<=,9,)||(string[i-l]>=,A,&&string[i-lJ<=,Z,)||(string[i-l]>=,a,&
&string[i-l]<=,z,))
{printf("\n输入的表达式有误!");returnERROR;}
else*pre_expr++=c;
}
elseif(c==,*,||c==7,)
{
while(GetTopl(S,&cl)&&(cl==lAl))
{Popl(&S,&cl);*pre_expr++=cl;}Pushl(&S,c);
}
elseif(c==l+,||€=='-•)
{
while(GetTopl(S,&cl)&&(cl==lAl| |cl==7'))
{Popl(&S,&cl);*pre_expr++=cl;}
Pushl(&S,c);
elseif(c==,A,)
}
else{printf("\n输入的表达式有误!");returnERROR;}
i-;
if(i>=0)c=string[i];
else
while(!StackEmptyl(S)&&GetTopl(S,&cl)&&cl!=,#')
{Poplf&S,&c);*pre_expr++=c;}
}
Popl(&S&c);
*pre_expr=,\0,;
if(i<0&&StackEmptyl(S))returnOK;
elsereturnERROR;
}
voidreversal_string(char*exprstring)
{
intlenJJ;
chartemp;
len=strlen(exprstring);
for(i=0,j=len-l;i<j;i++J~)
{
temp=exprstring[i];
exprstring[i]二exprstring[j];
exprstring[j]二temp;
}
}
voidWriteExprfBiTreeE)
{
if(E)
{
if(E->lchild&&E->lchild->==CHAR)
{
if(Pri_Compare(E->->lchild->)){printf(“(“);
WriteExpr(E->lchild);
printffT1);}
elseWriteExpr(E->lchild);
}
elseWriteExpr(E->lchild);
if(E->==INT){printf(,,%d,,/E->);}
elseprintf(,,%c,,/E->);
if(E->rchild&&E->rchild->==CHAR)if(Pri_Compare(E->->rchild->)){printf("(");WriteExpr(E->rchild);printf(")");}elseWriteExpr(E->rchild);
}
elseWriteExpr(E->rchild);
}
}
voidWriteExprl(BiTreeE)
{
if(E)
{
WriteExprl(E->lchild);
WriteExprl(E->rchild);
if(E->==INT){printf(,,%d,,/E->);}elseprintf(,,%c,,/E->);
}
}
voidAssign(BiTree*E,charVJntc,int*flag)
{
if(*E)
{
if((*E)->==CHAR&&(*E)->==V){(*E)->=INT;(*E)->=c;*flag=l;}Assign(&((*E)->lchild),V,c/flag);
Assign(&((*E)->rchild),V,c,flag);
}
}
longOperate(intoprl,charopr;intopr2)
{
longresult;
switch(opr)
{
case
result=oprl+opr2;
returnresult;break;
caseL,:
result=oprl-opr2;
returnresult;break;
case
result=oprl*opr2;
returnresult;break;
case7':
result=oprl/opr2;
returnresult;break;
case
result=power(oprl,opr2);
returnresult;break;
default:break;
}
}
StatusCheck(BiTreeE)
{
if(E&&E->==CHAR)
{
if(E->!='*1&&1>(血8丄!=穴&&E->data・c!=L&&E・>!='+‘&&E・>!=7‘){printf("\n表达式中仍存在变量没有赋值!没法求出表达式的值!”);returnERROR;}
if(Check(E->lchild))
Check(E->rchild);
}
}
longValuefBiTreeE)
{
if(E)
{
if(!E->lchild&&!E->rchild&&E->==INT)return(E->);
returnOperate(Value(E・>lchild),E・>data・cA/alue(E・>rchild));
}
}
intisoperator(charc)
{
switch(c)
{
casereturnTRUE;
caseL,:returnTRUE;
case⑷:returnTRUE;
case7':returnTRUE;
case,A,:returnTRUE;
default:returnFALSE;
}
}
voidmain()
{
BiTreeE;
intflag=O;
longresult;
charV;
intc;
charstring[30];
printf(“输入正确的前缀表达式的要求:(比如/*++abc-de*fg)”);
if(lnput_Expr(Expr_String,O))
if(ReadExpr(&E,Expr_String))
{flag=l;
printf("表达式构造成功!");
}
printf("\n二叉树凹入法表示为:\n");
ShowTree(E,5);
if(flag==l)
{printf("\n带括弧的中缀表达式为:");
WriteExpr(E);
}
elseprintf("\n表达式未构造成功!请重新构造成功的表达式!");
if(flag==l)
{printf("\n不带括弧的后缀表达式为:”);
WriteExprl(E);
}
elseprintf("\n表达式未构造成功!请重新构造成功的表达式!");
printf("\n前面前缀表达式对应的带括弧的中缀表达式为:");WriteExpr(E);if(lnput_Expr(stringzl))
if(Read_lnorder_Expr(string,Expr_String))
{reversaLstring(Expr_String);if(ReadExpr(&E,Expr_String)){flag=l;printfC,输入正确!
}
getch();
if(flag==l)