1、根据中缀表达式构造二叉树，再后序遍历求出后缀表达式。
#include<iostream> #include<string> using namespace std; //根据中缀表达式求出后缀表达式 typedef struct node { string v; node *l; node *r; }; void In2T(string In,node *&T) { if(T==NULL) { T=new node; T->l=T->r=NULL; } int op=9999999,idx=-1,ex=0; //a+(b+c)*d+e for(int i=In.length()-1; i>=0; i--) //找出优先级最低的运算符的位置，优先级越低深度越低 { if(In[i]==')') ex+=2; else if(In[i]=='(') ex-=2; else if(In[i]=='+'||In[i]=='-') { if(ex+1<op) { op=ex+1; idx=i; } } else if(In[i]=='*'||In[i]=='/') { if(ex+2<op) { op=ex+2; idx=i; } } } if(idx==-1)//没有运算符只有括号和数字 { int idx1,idx2; for(idx1=0; idx1<In.length(); ++idx1) if(In[idx1]!='(') break; for(idx2=In.length()-1; idx2>=0; --idx2) if(In[idx2]!=')') break; T->v=In.substr(idx1,idx2-idx1+1); return ; } T->v=In[idx]; In2T(In.substr(0,idx),T->l); In2T(In.substr(idx+1,In.length()-idx),T->r); } void dfs(node* T) { if(T==NULL) return; dfs(T->l); dfs(T->r); cout<<T->v; } int main() { string In; node *root=NULL; getline(cin,In); In2T(In,root); dfs(root); cout<<endl; return 0; }2、根据后缀表达式构造二叉树。
#include<iostream> #include<vector> #include<string> using namespace std; typedef struct node { char v; node* l; node* r; }; void dfs(node* &root) { if(root==NULL) return ; dfs(root->l); cout<<root->v; dfs(root->r); } int main() { string In; getline(cin,In); node* root=NULL; vector<node*> stk; for(int i=0; i<In.size(); ++i) { node* t=new node; t->v=In[i]; t->l=t->r=NULL; if(In[i]=='+'||In[i]=='-'||In[i]=='*'||In[i]=='/') { int s=stk.size(); node* tl=stk[s-2]; node* tr=stk[s-1]; stk.pop_back(); stk.pop_back(); t->l=tl; t->r=tr; stk.push_back(t); } else stk.push_back(t); root=t; } dfs(root); return 0; }
3、输入表达式，输出值。分两种情况：中缀表达式和后缀表达式。
中缀表达式求值：先将中缀表达式建立二叉树转后缀表达式，然后再求值。
#include <iostream> #include <string> #include <string.h> #include <math.h> #include <stdlib.h> using namespace std; string s[105]; int n=0; struct node { string v; node *l; node *r; }; void dfs(node *T) { if(T==NULL) return ; dfs(T->l); dfs(T->r); // cout<<T->v; s[n++]=T->v; } void f(string str,node *&T) { if(T==NULL) { T=new node; T->l=T->r=NULL; } int op=9999,ex=0,idx=-1; for(int i=str.length()-1; i>=0; i--) { if(str[i]==')') ex+=2; else if(str[i]=='(') ex-=2; else if(str[i]=='+'||str[i]=='-') { if(ex+1<op) { op=ex+1; idx=i; } } else if(str[i]=='*'||str[i]=='/') { if(ex+2<op) { op=ex+2; idx=i; } } } if(idx==-1) { int idx1,idx2; for(idx1=0; idx1<str.length(); idx1++) if(str[idx1]!='(') break; for(idx2=str.length()-1; idx2>=0; idx2--) if(str[idx2]!=')') break; T->v=str.substr(idx1,idx2-idx1+1); return ; } T->v=str[idx];//A+B f(str.substr(0,idx),T->l); f(str.substr(idx+1,str.length()-idx-1),T->r); } //12.23 double si(string s)//string转double { int i; double sum1=0,sum2=0; int st=-1;//小数点的位置 for(i=0; i<s.length(); i++) { if(s[i]=='.') { st=i; break; } } if(st==-1) { sum1=atof(s.c_str()); return sum1; } else { string t1=s.substr(0,st); string t2=s.substr(st+1,s.length()-st-1); sum1=atof(t1.c_str()); sum2=atof(t2.c_str()); return (sum1+sum2/pow(10,s.length()-st-1)); } } int main() { double a[105]; int i,num=0; memset(a,0,sizeof(a)); node *root=NULL; string str; getline(cin,str); f(str,root); dfs(root); cout<<"后缀表达式："<<endl; for(i=0; i<n; i++) cout<<s[i]; cout<<endl; cout<<"结果为："<<endl; for(i=0; i<n; i++) { if(s[i][0]>='0'&&s[i][0]<='9') { a[num++]=si(s[i]); } else if(s[i][0]=='+') { double t1=a[num-2]; double t2=a[num-1]; a[num-1]=0; a[num-2]=0; num-=2; a[num++]=t1+t2; } else if(s[i][0]=='-') { double t1=a[num-2]; double t2=a[num-1]; a[num-1]=0; a[num-2]=0; num-=2; a[num++]=t1-t2; } else if(s[i][0]=='*') { double t1=a[num-2]; double t2=a[num-1]; a[num-1]=0; a[num-2]=0; num-=2; a[num++]=t1*t2; } else if(s[i][0]=='/') { double t1=a[num-2]; double t2=a[num-1]; a[num-1]=0; a[num-2]=0; num-=2; a[num++]=t1/t2; } } cout<<a[0]<<endl; return 0; }
