求解，程序设计
二叉树求解表达式用（c语言）
代码还是搜的，求修改
//二叉树上的表达式求值算法
#include
#include
#include
#define Max 100
typedef struct
{
char *data;
int top;
int stacksize;
}seqstack1;
typedef struct Tree
{
char data1[Max];
float data2;
struct Tree *lchild,*rchild;
}*BiTree,Bnode;
typedef struct
{
BiTree *data;
int top;
int stacksize;
}seqstack2;
//运算符栈
int initstack1(seqstack1 *L)
{
L->data=(char *)malloc(Max * sizeof(char));
if(L->data==NULL) exit(0);
L->top=-1;
L->stacksize=Max;
return 1;
}
int pushstack1(seqstack1 *L,char ch)
{
if(L->top==L->stacksize-1)
{
printf("栈满!\n"); return 0;
}
L->top++;
L->data[L->top]=ch;
return 1;
}
char popstack1(seqstack1 *L)
{
if(L->top==-1)
printf("@空栈!\n");
else
return L->data[L->top--];
}
char gettop1(seqstack1 L)
{
if(L.top==-1)
printf("!!空栈!\n");
else
return L.data[L.top];
}
//操作数栈
int initstack2(seqstack2 *L)
{
L->data=(BiTree *)malloc(Max * sizeof(BiTree));
if(L->data==NULL) exit(0);
L->top=-1;
L->stacksize=Max;
return 1;
}
int pushstack2(seqstack2 *L,BiTree T)
{
if(L->top==L->stacksize-1)
{
printf("栈满!\n"); return 0;
}
L->top++;
L->data[L->top]=T;
return 1;
}
int popstack2(seqstack2 *L,BiTree T)
{
if(L->top==-1)
{ printf("?空栈!\n"); return 0;}
T=L->data[L->top];
L->top--;
return 1;
}
int gettop2(seqstack2 L,BiTree T)
{
if(L.top==-1)
{ printf("空栈!\n"); return 0;}
T=L.data[L.top];
return 1;
}
//求值栈
int prior(char str1,char str2)
{
switch(str1)
{
case '#':case'(':case'[':return 0;break;
case '*':case '/':return 1;break;
case '+':case'-':switch(str2)
{
case '+':case'-':case'#':return 1;break;
case '*':case '/':return 0;break;
}break;
}
}
int indigit(char ch)
{
if(ch>='0'&&ch<='9'||ch=='.')
return 1;
else
return 0;
}
float calculate(float a,float b,char ch)
{
if(strcmp(ch,"")==0)
return (a*b);
else if(strcmp(ch,"/")==0)
return (a/b);
else if(strcmp(ch,"+")==0)
return (a+b);
else
return (a-b);
}
float transform(char *ch)
{
double result=0,result1=0,result2=0;
char str[20];
int i=0,k=0;
while(ch[i]>='0'&&ch[i]<='9')
{
result1=result1*10+ch[i]-'0';
i++;
}
if(ch[i]=='\0')
return result1;
else
{
while(ch[i]!='\0')
{
str[k]=ch[i];
k++;i++;
}
str[k]='\0';
k--;
while(str[k]!='.')
{
result2=result2*0.1+str[k]-'0';
k--;
}
result2=result2*0.1;
result=result1+result2;
return result;
}
}
//建子叶
void createleaf(BiTree T,char *ch,seqstack2 *L2)
{
float n;
T=(Bnode *)malloc(sizeof(Bnode));
if(T==NULL) exit(0);
n=transform(ch);
strcpy(T->data1,ch);
T->data2=n;
T->lchild=T->rchild=NULL;
pushstack2(L2,T);
}
//建子树
void createtree(BiTree T,char *ch,BiTree rchild,BiTree lchild,seqstack2 *L2)
{
float n;
ch[1]='\0';
T=(Bnode *)malloc(sizeof(Bnode));
if(T==NULL) exit(0);
popstack2(L2,rchild);
popstack2(L2,lchild);
n=calculate(lchild->data2,rchild->data2,ch);
T->data2=n; strcpy(T->data1,ch);
T->rchild=rchild; T->lchild=lchild;
pushstack2(L2,T);
}
//表达式转换为二叉树存储
BiTree Tobitree(char *p)
{
seqstack1 L1;
seqstack2 L2;
int i=0,j=0;
BiTree T,lchild,rchild;
char str[20],ch;
initstack1(L1);
pushstack1(L1,'#');
initstack2(L2);
while(p[i]!='\0')
{
if(indigit(p[i]))
{
while(indigit(p[i]))
{
str[j++]=p[i];
i++;
}
str[j]='\0';
createleaf(T,str,L2);
j=0; i--;
}
else
{
switch(p[i])
{
case '(':case '[':pushstack1(L1,p[i]);break;
case ')':ch=popstack1(L1);
while(ch!='(')
{
createtree(T,&ch,rchild,lchild,L2);
ch=popstack1(L1);
}
break;
case ']':ch=popstack1(L1);
while(ch!='[')
{
createtree(T,&ch,rchild,lchild,L2);
ch=popstack1(L1);
}
break;
default:
ch=gettop1(L1);
while(prior(ch,p[i]))
{
createtree(T,&ch,rchild,lchild,L2);
ch=popstack1(L1); ch=gettop1(L1);
}
pushstack1(L1,p[i]);
break;
}
}
i++;
}
popstack2(L2,T);
return T;
}
//后序遍历表达式树
void postorder(BiTree T)
{
if(T)
{
postorder(T->lchild);
postorder(T->rchild);
printf("%s ",T->data1);
}
}
//先序遍历表达式树
void midorder(BiTree T)
{
if(T)
{
midorder(T->lchild);
printf("%s ",T->data1);
midorder(T->rchild);
}
}
void main()
{
char *p;
BiTree T;
p=(char *)malloc(Max * sizeof(char));
printf("输入表达式(以#号结束):");
scanf("%s",p);
T=Tobitree(p);
printf("后缀式为:");
postorder(T);
printf("\n");
printf("前缀式为");
midorder(T);
printf("\n");
printf("结果为:");
printf("%.3f\n",T->data2);
}
