表达式二叉树代码
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef int Status;
typedef enum{INT,CHAR}ElemTag;
typedef struct TElemType
{
ElemTag tag;
union
{
int num;
char c;
};
} TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef BiTree SElemType;
typedef char SElemType1;
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 2
typedef struct SqStack
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
typedef struct SqStack1
{
SElemType1 *base;
SElemType1 *top;
int stacksize;
}SqStack1;
Status InitStack(SqStack *S)
{
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW);
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.top==S.base) return TRUE;
else return FALSE;
}
Status Push(SqStack *S,SElemType e)
{
if((*S).top-(*S).base>=(*S).stacksize)
{
(*S).base=(SElemType
*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e)
{
if((*S).top==(*S).base) return ERROR;
*e=*--(*S).top;
return OK;
}
Status GetTop(SqStack S,SElemType *e)
{
if(S.top>S.base)
{
*e=*(S.top-1);
return OK;
}
else
return ERROR;
}
Status InitStack1(SqStack1 *S)
{
(*S).base=(SElemType1 *)malloc(STACK_INIT_SIZE*sizeof(SElemType1));
if(!(*S).base)
exit(OVERFLOW);
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty1(SqStack1 S)
{
if(S.top==S.base) return TRUE;
else return FALSE;
}
Status Push1(SqStack1 *S,SElemType1 e)
{
if((*S).top-(*S).base>=(*S).stacksize)
{
(*S).base=(SElemType1
*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType1));
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
Status Pop1(SqStack1 *S,SElemType1 *e)
{
if((*S).top==(*S).base) return ERROR;
*e=*--(*S).top;
return OK;
}
Status GetTop1(SqStack1 S,SElemType1 *e)
{
if(S.top>S.base)
{
*e=*(S.top-1);
return OK;
}
else
return ERROR;
}
long power(int x,int exp)
{
long result;
int i;
for(i=1,result=1;i
result*=x;
return result;
}
#include"expression.h"
#include
int save_number[51];
char Expr_String[50];
Status Input_Expr(char *string,int flag)
{
if(flag==0)printf("\n请输入正确的前缀表示式:");
else printf("\n输入前面前缀表达式对应的带括弧的中缀表示式:");
flushall();
gets(string);
if(strlen(string)==1)
if(string[0]=='+'||string[0]=='-'||string[0]=='*'||string[0]=='/'||string[0]=='^') { printf("\n表达式只有一个字符,为运算符,错误!");return ERROR;}
else
if((string[0]>='0'&&string[0]='a'&&string[0]='A'&&string[0]
{ printf("\n表达式只有一个字符!");return OK;}
else {printf("\n输入的字符不是运算符也不是变量常量,错误!");return ERROR;} return OK;
}
void judge_value(BiTree *E,char *string,int i)
{
if(string[i]>='0'&&string[i]
{(*E)->data.tag=INT;(*E)->data.num=string[i]-48;}
else if(string[i]>=1&&string[i]
{(*E)->data.tag=INT;(*E)->data.num=save_number[string[i]];}
else
{(*E)->data.tag=CHAR;(*E)->data.c=string[i];}
}
Status ReadExpr(BiTree *E,char *exprstring)
{
SqStack S;
int i,len;
BiTree p,q;
(*E)=(BiTree)malloc(sizeof(BiTNode));
(*E)->lchild=NULL;
(*E)->rchild=NULL;
len=strlen(exprstring);
if(len==1)
judge_value(E,exprstring,0);
else
{
judge_value(E,exprstring,0);
InitStack(&S);
q=(*E);
Push(&S,q);
Push(&S,q);
for(i=1;i
{
p=(BiTree)malloc(sizeof(BiTNode));
judge_value(&p,exprstring,i);
p->lchild=NULL;
p->rchild=NULL;
if(exprstring[i]=='+'||exprstring[i]=='-'||exprstring[i]=='*'||exprstring[i]=='/'||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) return OK;
else
{
printf("\n输入的表达式有误!");
return ERROR;
}
}
}
void ShowTree(BiTree& E,int t)
{
int i;
if(E)
{
ShowTree(E->rchild,t+5);
for(i=0;i
{printf(" ");}
printf("%5c\n",E->data.c);
ShowTree(E->lchild,t+5);
}
}
Status Pri_Compare(char c1,char c2)
{
if((c1=='^'||c1=='*'||c1=='-'||c1=='+'||c1=='/')&&(c2=='^'||c2=='*'||c2=='-'||c2=='+'||c2=='/'))
{
if(c1=='^')
{
if(c2!='^') return OK;
else return ERROR;
}
if(c1=='*'||c1=='/')
{
if(c2=='^') return ERROR;
else return OK;
}
else return ERROR;
}
else return ERROR;
}
Status Read_Inorder_Expr(char *string,char *pre_expr)
{
int i,j,len,char_number=1;
int number;
char c,c1;
SqStack1 S;
InitStack1(&S);
Push1(&S,'#');
len=strlen(string);
c=string[len-1];
i=len-1;
while(!StackEmpty1(S)&&i>=0)
{
if(c=='(')
Pop1(&S,&c);
while(c!=')')
{
*pre_expr++=c;
if(!StackEmpty1(S)&&GetTop1(S,&c1)&&c1!='#') Pop1(&S,&c);
else {printf("\n输入的表达式有误!");return ERROR;}
}
}
else if(c==')')
{
Push1(&S,c);
}
else if(c>='0'&&c
{
number=c-48;
for(c1=string[i-1],j=1;(c1>='0'&&c1=0;j++,i--)
{
number=(c1-48)*power(10,j)+number;
c1=string[i-2];
}
save_number[char_number]=number; *pre_expr++=char_number++;
}
else if((c>='a'&&c='A'&&c
{
if((string[i-1]>='0'&&string[i-1]='A'&&string[i-1]='a'&&string[i-1]
{printf("\n输入的表达式有误!");return ERROR;}
else *pre_expr++=c;
}
else if(c=='*'||c=='/')
{
while(GetTop1(S,&c1)&&(c1=='^'))
{Pop1(&S,&c1);*pre_expr++=c1;}
Push1(&S,c);
}
else if(c=='+'||c=='-')
{
while(GetTop1(S,&c1)&&(c1=='^'||c1=='*'||c1=='/'))
{Pop1(&S,&c1);*pre_expr++=c1;}
Push1(&S,c);
}
else if(c=='^')
Push1(&S,c);
}
else {printf("\n输入的表达式有误!");return ERROR;}
i--;
if(i>=0) c=string[i];
else
while(!StackEmpty1(S)&&GetTop1(S,&c1)&&c1!='#')
{Pop1(&S,&c);*pre_expr++=c;}
}
Pop1(&S,&c);
*pre_expr='\0';
if(i
else return ERROR;
}
void reversal_string(char *exprstring)
{
int len,i,j;
char temp;
len=strlen(exprstring);
for(i=0,j=len-1;i
{
temp=exprstring[i];
exprstring[i]=exprstring[j];
exprstring[j]=temp;
}
}
void WriteExpr(BiTree E)
{
if(E)
{
if(E->lchild&&E->lchild->data.tag==CHAR)
{
if(Pri_Compare(E->data.c,E->lchild->data.c))
{printf("(");
WriteExpr(E->lchild);
printf(")");}
else WriteExpr(E->lchild);
}
else WriteExpr(E->lchild);
if(E->data.tag==INT){printf("%d",E->data.num);}
else printf("%c",E->data.c);
if(E->rchild&&E->rchild->data.tag==CHAR)
{
if(Pri_Compare(E->data.c,E->rchild->data.c))
{printf("(");WriteExpr(E->rchild);printf(")");}
else WriteExpr(E->rchild);
}
else WriteExpr(E->rchild);
}
}
void WriteExpr1(BiTree E)
{
if(E)
{
WriteExpr1(E->lchild);
WriteExpr1(E->rchild);
if(E->data.tag==INT){printf("%d",E->data.num);}
else printf("%c",E->data.c);
}
}
void Assign(BiTree *E,char V,int c,int *flag)
{
if(*E)
{
if((*E)->data.tag==CHAR&&(*E)->data.c==V)
{(*E)->data.tag=INT;(*E)->data.num=c;*flag=1;}
Assign(&((*E)->lchild),V,c,flag);
Assign(&((*E)->rchild),V,c,flag);
}
}
long Operate(int opr1,char opr,int opr2)
{
long result;
switch(opr)
{
case '+':
result=opr1+opr2;
return result;break;
case '-':
result=opr1-opr2;
return result;break;
case '*':
result=opr1*opr2;
return result;break;
case '/':
result=opr1/opr2;
return result;break;
case '^':
result=power(opr1,opr2);
return result;break;
default:break;
}
}
Status Check(BiTree E)
{
if(E&&E->data.tag==CHAR)
{
if(E->data.c!='*'&&E->data.c!='^'&&E->data.c!='-'&&E->data.c!='+'&&E->data.c!='/') {printf("\n表达式中仍存在变量没有赋值!没法求出表达式的值!");return ERROR;}
if(Check(E->lchild))
Check(E->rchild);
}
}
long Value(BiTree E)
{
if(E)
{
if(!E->lchild&&!E->rchild&&E->data.tag==INT) return (E->data.num);
return Operate(Value(E->lchild),E->data.c,Value(E->rchild));
}
}
int isoperator(char c)
{
switch(c)
{
case '+': return TRUE;
case '-': return TRUE;
case '*': return TRUE;
case '/': return TRUE;
case '^': return TRUE;
default: return FALSE;
}
}
void main()
{
BiTree E;
int flag=0;
long result;
char V;
int c; char string[30]; printf("输入正确的前缀表达式的要求:(比如/*++abc-de*fg)"); if(Input_Expr(Expr_String,0)) if(ReadExpr(&E,Expr_String)) {flag=1; printf("表达式构造成功!"); } printf("\n二叉树凹入法表示为:\n"); ShowTree(E,5); if(flag==1)
{printf("\n带括弧的中缀表达式为:");
WriteExpr(E);
}
else printf("\n表达式未构造成功!请重新构造成功的表达式!");
if(flag==1)
{printf("\n不带括弧的后缀表达式为:");
WriteExpr1(E);
}
else printf("\n表达式未构造成功!请重新构造成功的表达式!");
printf("\n前面前缀表达式对应的带括弧的中缀表达式为:");WriteExpr(E); if(Input_Expr(string,1))
if(Read_Inorder_Expr(string,Expr_String))
{
reversal_string(Expr_String);
if(ReadExpr(&E,Expr_String))
{flag=1;printf("输入正确!");;}
}
getch();
if(flag==1)
{
AS: int Assign_flag=0;
printf("\n表达式E 为:"); WriteExpr(E); flushall(); printf("\n请输入要赋值的字符:"); V=getchar(); printf("请输入要将赋值为:"); scanf("%d",&c); Assign(&E,V,c,&Assign_flag); if(Assign_flag)
{
printf("赋值成功!赋值后的表达式为:");
WriteExpr(E);
}
else
printf("\n表达式里没有%c这个变量!",V);
printf("\n是否赋值(y/n):");
if(getch()=='y')
{
goto AS;
}
}
else printf("\n表达式未构造成功!请构造成功的表达式!"); getch();
if(flag==1)
{
printf("\n算数表达式:");WriteExpr(E);
if(Check(E))
{result=Value(E);printf("\n求算数表达值:");WriteExpr(E);printf("=%ld",result);}
}
else printf("\n表达式未构造成功!请构造成功的表达式!"); getch();
printf("\n请按任意键退出!");
getch();
exit(0);
}
式的