200,用二叉树把中缀表达式转为后缀表达式
发布网友
发布时间：2022-05-27 19:16
共3个回答
热心网友
时间：2023-09-13 19:34
#define max 100
typedef struct node{
char a[max];
struct node *lchild,*rchild;
}bintree;
int count=0;
char array[max];
bintree * init(bintree * L)
{
L=(bintree *)malloc(sizeof(bintree));
L->rchild=L->lchild=NULL;
return L;
}
enter ()
{
int i=-1;
do
{
i++;
array[i]=getch();
putch(array[i]);
if(array[i]=='\b')
i=i-2;
if (array[i]=='='||array[i]=='\r') break;
}while(1);
if(array[i]=='\r') array[i]='=';
array[i+1]='\0';
}
char getfromarray(bintree **L)
{
int i=0;
while(array[count]<='9'&&array[count]>='0'){
(*L)->a[i]=array[count];
i++;
count++;
}
(*L)->a[i]='\0';count++;
return array[count-1];
}
bintree * createtree(bintree *L)
{
bintree *p,*q;
char a;
if(L==NULL) L=p=init(p);
a=getfromarray(&L);
while(a!='=')
{ q=init(q);
q->a[0]=a;
q->a[1]='\0';
switch(a)
{
case '+':
case '-': q->lchild=L;L=q; p=init(p);a=getfromarray(&p);L->rchild=p;break;
case '*':
case '/':
if(L->a[0]=='+'||L->a[0]=='-')
{p=init(p);strcpy(p->a,L->a);p->lchild=L;p->rchild=q;a=getfromarray(&L);L=p;}
else
{q->lchild=L;L=q;p=init(p);a=getfromarray(&p);L->rchild=p;}
break;
case '(': p=L;while(p->rchild) p=p->rchild;
if(p->lchild==NULL)
{ p->lchild=createtree(p->lchild);a=array[count];count++;break;}
else
{ p->rchild=createtree(p->rchild);a=array[count];count++;break;}
case ')': return L;
}
}
return L;
}
output(bintree *L)
{
if(L)
{
output(L->lchild);
output(L->rchild);
printf("%s ",L->a);
}
}
void main()
{
bintree *L=NULL;
clrscr();
enter();
L=createtree(L);
output(L);
}
热心网友
时间：2023-09-13 19:34
这个用二叉树比较难实现，以下我用的是表达式的方法把中缀变为后缀：
如图所示：
（另外一个知道中找到的http://zhidao.baidu.com/question/261765295.html?an=0&si=2）
热心网友
时间：2023-09-13 19:34
