p=p->next; }
printf("=%d ",n); }
void houzhui(Lnode *p) //中缀表达式转化为后缀表达式
{sqstack2 OPTR; //运算符栈 Lnode *r,*q,*head; int n; char c,c2;
InitStack2(OPTR); p=p->next;
q=(Lnode*)malloc(sizeof(struct Node)); head=q;
while(p)
{ switch(p->data) {case 1:n=p->data1;
r=(Lnode*)malloc(sizeof(struct Node)); q->next=r; q=q->next; q->data=1; q->data1=n; break;
case 2:c=p->data2;
if(stackempy2(OPTR)) Push2(OPTR,c); else { switch(c)
{ case '(': Push2(OPTR,c);break; case ')': Popopnd2(OPTR,c2); while(c2!='(')
{ r=(Lnode*)malloc(sizeof(struct Node)); q->next=r; q=q->next; q->data=2; q->data2=c2; Popopnd2(OPTR,c2); }
break;
default: GetTop2(OPTR,c2); while(!compare(c2,c)) { Popopnd2(OPTR,c2);
r=(Lnode*)malloc(sizeof(struct Node)); q->next=r; q=q->next; q->data=2; q->data2=c2; GetTop2(OPTR,c2); }
Push2(OPTR,c); break; } } break;
default: printf("结点有误"); break; }
p=p->next; }
while(!stackempy2(OPTR)) { Popopnd2(OPTR,c2);
r=(Lnode*)malloc(sizeof(struct Node)); q->next=r; q=q->next; q->data=2; q->data2=c2; }
q->next=NULL; q=head->next; while(q)
{if(q->data==1) printf("%d ",q->data1); if(q->data==2) printf("%c",q->data2); q=q->next; }
houzhuiqiuzhi(head,n);
printf("=%d ",n); }
void qianzhuiqiuzhi(Lnode2 *p,int &e) //前缀表达式求值 {sqstack1 OPND; //运算数栈
sqstack2 OPTR; //运算符栈 int n; char c;
Lnode2 *head; head=p;
p=p->next; InitStack1(OPND); InitStack2(OPTR); while(p!=head) {switch(p->data) {case 1:n=p->data1; Push1(OPND,n); break;
case 2:c=p->data2; Push2(OPTR,c);
Operatqianzhui(OPND,OPTR); break;
default:printf("结点有误"); break; }
p=p->next; }
Popopnd1(OPND,n); e=n; }
void qianzhui(Lnode *p) 式
{sqstack2 OPTR; //运算符栈 InitStack2(OPTR); int n; char c,c2; Lnode *first;
Lnode2 *q,*head,*r,*head2,*s; first=p;
p=p->next;
q=(Lnode2*)malloc(sizeof(struct Node2)); //中缀表达式转化为前缀表达//建立存中缀表达式的双向循环
链表 head=q; while(p)
{r=(Lnode2*)malloc(sizeof(struct Node2)); q->next=r; r->prior=q; q=q->next;
q->data=p->data; q->data1=p->data1; q->data2=p->data2; p=p->next; }
q->next=head; head->prior=q;
s=(Lnode2*)malloc(sizeof(struct Node2)); //建立存前缀表达式的双向循环链表 head2=s;
while(q!=head) {switch(q->data) {case 1:n=q->data1; r=(Lnode2*)ma
lloc(sizeof(struct Node2)); s->next=r; r->prior=s; s=s->next; s->data=1; s->data1=n; break;
case 2:c=q->data2;
if(stackempy2(OPTR)) Push2(OPTR,c); else
{ GetTop2(OPTR,c2);
if(c2==')') Push2(OPTR,c); else{ switch(c)
{ case ')':Push2(OPTR,c);break; case '(': Popopnd2(OPTR,c2); while(c2!=')')
{ r=(Lnode2*)malloc(sizeof(struct Node2)); s->next=r;
r->prior=s; s=s->next; s->data=2; s->data2=c2; Popopnd2(OPTR,c2); }
break;
default: GetTop2(OPTR,c2); while(!compare(c2,c)) { Popopnd2(OPTR,c2);
r=(Lnode2*)malloc(sizeof(struct Node2)); s->next=r; r->prior=s; s=s->next; s->data=2; s->data2=c2; GetTop2(OPTR,c2); }
Push2(OPTR,c); break; } } }
break;
default:printf("结点有误"); break; }
q=q->prior; }
while(!stackempy2(OPTR)) { Popopnd2(OPTR,c2);
r=(Lnode2*)malloc(sizeof(struct Node2)); s->next=r; r->prior=s; s=s->next; s->data=2; s->data2=c2; }
s->next=head2; head2->prior=s; while(s!=head2)
{if(s->data==1) printf("%d ",s->data1);