转载了大神的一篇文章，关于表达式的二叉树遍历

2019-11-06 09:04:06

字体：大中小

来源：转载

供稿：网友

给出一个由加减乘除和括号构成的表达式计算表达式的值和表达式的前缀和后缀表达式

[cpp] view plain copy

#include<stdio.h> #include<string.h> #include<math.h> #define Inf 1e9 struct tree { double date; char ch; tree *l,*r; tree() { ch='/0'; date=0; l=r=NULL; } }; double judge(char *s,int x,int y,double &n) { double num=0; int i,ok=0; for(i=x; i<y; i++) if(s[i]>='0'&&s[i]<='9') { if(!ok)num=num*10+s[i]-'0'; else num+=(s[i]-'0')*pow(10,ok-i); } else if(s[i]=='.'){ok=i;} else return 0; return n=num; } tree *build(char *s,int x,int y) { tree *now=new tree; double num=Inf; judge(s,x,y,num); //PRintf("%c/n",s[x]); if(num!=Inf) { now->date=num; return now; } int p=0,c1=-1,c2=-1; for(int i=x; i<y; i++) switch(s[i]) { case '(':p++;break; case ')':p--;break; case '+':case '-':if(!p)c1=i;break; case '*':case '/':if(!p)c2=i;break; } if(c1<0)c1=c2; if(c1<0)return build(s,x+1,y-1); now->l=build(s,x,c1); now->r=build(s,c1+1,y); now->ch=s[c1]; return now; } double dfs(tree *p) { if(!p)return 0; if(p->l==p->r&&p->l==NULL)return p->date; switch (p->ch) { case '+':return p->date=dfs(p->l)+dfs(p->r);break; case '-':return p->date=dfs(p->l)-dfs(p->r);break; case '*':return p->date=dfs(p->l)*dfs(p->r);break; case '/':return p->date=dfs(p->l)/dfs(p->r);break; } return 0; } void dfs(tree *p,int choose) { if(!p)return ; if(p->l==p->r&&p->l==NULL){printf(" %g",p->date);} if(!choose){printf("%c",p->ch);dfs(p->l,choose);dfs(p->r,choose);} else { dfs(p->l,choose);dfs(p->r,choose);printf("%c",p->ch); } } char s[1005]; int main() { tree *root=NULL; while(gets(s)==NULL) { root=NULL; int len=strlen(s); root=build(s,0,len); double ans=dfs(root); puts("前缀表达式：");dfs(root,0);puts(""); puts("后缀表达式：");dfs(root,1);puts(""); printf("%s=%g/n",s,ans); } return 0; }

上面的不能计算5*-6这种，下面的进行了改正

[cpp] view%20plain copy

#include<stdio.h> #include<string.h> #include<math.h> #define Inf 1e9 struct tree { double date; char ch; tree *l,*r; tree() { ch='/0'; date=0; l=r=NULL; } }; char st[1005]; double judge(char *s,int x,int y,double &n) { double num=0; int i,ok=0; for(i=x; i<y; i++) if(s[i]>='0'&&s[i]<='9') { if(!ok)num=num*10+s[i]-'0'; else num+=(s[i]-'0')*pow(10,ok-i); } else if(s[i]=='.'){ok=i;} else return 0; return n=num; } int is_Operator(char c) { if(c=='+'||c=='-'||c=='*'||c=='/')return 1; return 0; } tree *build(char *s,int x,int y) { tree *now=new tree; double num=Inf; judge(s,x,y,num); //printf("%c/n",s[x]); if(num!=Inf) { now->date=num; return now; } int p=0,c1=-1,c2=-1; for(int i=x; i<y; i++)if(s[i]=='-'&&is_operator(s[i-1])) { int t=2; st[0]='('; st[1]='0'; int k=0,ok=1; for(int j=i; j<y; j++) { if(s[i]=='(')k++; else if(s[i]==')')k--; st[t++]=s[j]; if((ok&&j==y-1)||(!k&&is_operator(s[i+1]))) { ok=0; st[t++]=')'; } } s[t]='/0'; memcpy(s+i,st,sizeof(st)); i--; y+=3; } else switch(s[i]) { case '(':p++;break; case ')':p--;break; case '+': case '-':if(!p)c1=i;break; case '*':case '/':if(!p)c2=i;break; } if(c1<0)c1=c2; if(c1<0)return build(s,x+1,y-1); now->l=build(s,x,c1); now->r=build(s,c1+1,y); now->ch=s[c1]; return now; } double dfs(tree *p) { if(!p)return 0; if(p->l==p->r&&p->l==NULL)return p->date; switch (p->ch) { case '+': return p->date=dfs(p->l)+dfs(p->r); break; case '-': return p->date=dfs(p->l)-dfs(p->r); break; case '*': return p->date=dfs(p->l)*dfs(p->r); break; case '/': return p->date=dfs(p->l)/dfs(p->r); break; } return 0; } void dfs(tree *p,int choose) { if(!p)return ; if(p->l==p->r&&p->l==NULL) { printf(" %g",p->date); } if(!choose) { printf("%c",p->ch); dfs(p->l,choose); dfs(p->r,choose); } else { dfs(p->l,choose); dfs(p->r,choose); printf("%c",p->ch); } } char s[1005]; int main() { tree *root=NULL; while(gets(s)!=NULL) { root=NULL; int len=strlen(s); root=build(s,0,len); double ans=dfs(root); puts("前缀表达式："); dfs(root,0); puts(""); puts("后缀表达式："); dfs(root,1); puts(""); printf("%s=%g/n",s,ans); } return 0; }

上一篇：深入浅出SVM（持续更新）

下一篇：关于MyEclipse的使用