# 表达式类型的实现(二叉树)

void SetData(char _data); void SetLeft(TreeNode* _left); void SetRight(TreeNode* _right); TreeNode* GetLeft(); TreeNode* GetRight(); private: char Data; TreeNode* left,*right; }; //-------------------- 二叉树几及表达式类 class BinaryTreeAndExpr { public: BinaryTreeAndExpr(); ~BinaryTreeAndExpr(); TreeNode* GetRoot(); void SetRoot(TreeNode* _root); void ReadExpr(char* E); void WriteExpr(char* E); void Assign(char v,int c); static int Value(char* E); static BinaryTreeAndExpr* CompoundExpr(char p,char* E1,char* E2); void Release(); private: void ReleaseRecursion(TreeNode* &p); void ReadExprRecursion(TreeNode* &p,char* E); void WriteExprRecursion(TreeNode* p,char* E); void AssignRecursion(TreeNode* p,char v,int c); int ValueRecursion(TreeNode* p); int Priority(char c1,char c2); bool IsOperator(char c); int Evaluation(int a,char op,int b); TreeNode* root; int Expr_i,Expr_len; }; #endif 2、Expression.cpp 文件的实现 #include<iostream>

#include<cmath> #include"Expression.h" using namespace std; //----------------------树节点类成员函数 TreeNode::TreeNode(char _data,TreeNode* _left,TreeNode* _right) { Data=_data; left=_left; right=_right; } TreeNode::~TreeNode() { } char TreeNode::GetData() { return Data; } void TreeNode::SetLeft(TreeNode* _left) { left=_left; } void TreeNode::SetRight(TreeNode* _right) { right=_right; } TreeNode* TreeNode::GetLeft() { return left; } TreeNode* TreeNode::GetRight() { return right; } void TreeNode::SetData(char _data) { Data=_data; }

//---------------------------- 二叉树几及表达式类成员函数 BinaryTreeAndExpr::BinaryTreeAndExpr():root(NULL) { Expr_i=Expr_len=0; } BinaryTreeAndExpr::~BinaryTreeAndExpr() { } void BinaryTreeAndExpr::Release() { if(root!=NULL) { ReleaseRecursion(root); delete(root); root=NULL; } } void BinaryTreeAndExpr::ReleaseRecursion(TreeNode* &p) { if(p->GetLeft()!=NULL) { TreeNode* p1; p1=p->GetLeft(); ReleaseRecursion(p1); delete(p1); } else if(p->GetRight()!=NULL) { TreeNode*p2; p2=p->GetRight(); ReleaseRecursion(p2); delete(p2); } p=NULL; } TreeNode* BinaryTreeAndExpr::GetRoot() { return root; }

void BinaryTreeAndExpr::ReadExpr(char* E) { if(root!=NULL) {Release();root=NULL;} Expr_i=0; Expr_len=strlen(E); if(Expr_len==0) return ; ReadExprRecursion(root,E); } void BinaryTreeAndExpr::ReadExprRecursion(TreeNode* &p,char* E) { if(Expr_i==Expr_len)return ; p=(TreeNode*)new TreeNode(E[Expr_i++],NULL,NULL); char temp=p->GetData(); if(!IsOperator(temp)) return ; else { TreeNode* q1,* q2; ReadExprRecursion(q1,E); p->SetLeft(q1); ReadExprRecursion(q2,E); p->SetRight(q2); } } void BinaryTreeAndExpr::WriteExpr(char* E) { if(root==NULL) {E[0]='\0';return ;} WriteExprRecursion(root,E); } void BinaryTreeAndExpr::WriteExprRecursion(TreeNode* p,char* E) { char c1,c2,c3[100],c4[100]; if(p->GetLeft()==NULL || p->GetRight()==NULL) { E[0]=p->GetData(); E[1]='\0'; return ; } c1=p->GetLeft()->GetData(); c2=p->GetRight()->GetData();

if(!IsOperator(c1) && !IsOperator(c2)) { E[0]=c1;E[1]=p->GetData();E[2]=c2;E[3]='\0'; } else if(IsOperator(c1) && !IsOperator(c2)) { WriteExprRecursion(p->GetLeft(),c3); if(Priority(p->GetData(),p->GetLeft()->GetData())>0) { E[0]='('; for(int i=0;i<strlen(c3);i++) E[i+1]=c3[i]; E[i+1]=')'; E[i+2]=p->GetData(); E[i+3]=p->GetRight()->GetData(); E[i+4]='\0'; } else { for(int i=0;i<strlen(c3);i++) E[i]=c3[i]; E[i]=p->GetData(); E[i+1]=p->GetRight()->GetData(); E[i+2]='\0'; } } else if(!IsOperator(c1) && IsOperator(c2)) { WriteExprRecursion(p->GetRight(),c3); if(Priority(p->GetData(),p->GetRight()->GetData())>0) { E[0]=p->GetLeft()->GetData(); E[1]=p->GetData(); E[2]='('; for(int i=0;i<strlen(c3);i++) E[i+3]=c3[i]; E[i+3]=')'; E[i+4]='\0'; } else { E[0]=p->GetLeft()->GetData(); E[1]=p->GetData(); for(int i=0;i<strlen(c3);i++) E[i+2]=c3[i]; E[i+2]='\0'; } }

else { WriteExprRecursion(p->GetLeft(),c3); WriteExprRecursion(p->GetRight(),c4); if(Priority(p->GetData(),p->GetLeft()->GetData())>0) { E[0]='('; for(int i=0;i<strlen(c3);i++) E[i+1]=c3[i]; E[i+1]=')'; E[i+2]='\0'; } else { for(int i=0;i<strlen(c3);i++) E[i]=c3[i]; E[i]='\0'; } int j=strlen(E); E[j]=p->GetData(); if(Priority(p->GetData(),p->GetRight()->GetData())>0) { E[j+1]='('; for(int i=0;i<strlen(c4);i++) E[j+2+i]=c4[i]; E[j+2+i]=')'; E[j+3+i]='\0'; } else { for(int i=0;i<strlen(c4);i++) E[j+1+i]=c4[i]; E[j+1+i]='\0'; } } } int BinaryTreeAndExpr::Priority(char c1,char c2) { switch(c1) { case '+': case '-': return -1; case '*':

switch(c2) { case '+': case '-': return 1; } return -1; case '/': switch(c2) { case '+': case '-': return 1; } return -1; case '^': return 1; } return 0; } bool BinaryTreeAndExpr::IsOperator(char c) { return !(c>=97 && c<=122 || c>=48 && c<=57); } void BinaryTreeAndExpr::Assign(char v,int c) { AssignRecursion(root,v,c); } void BinaryTreeAndExpr::AssignRecursion(TreeNode* p,char v,int c) { if(p!=NULL) { if(p->GetData()==v) p->SetData(c+48); AssignRecursion(p->GetLeft(),v,c); AssignRecursion(p->GetRight(),v,c); } } BinaryTreeAndExpr* BinaryTreeAndExpr::CompoundExpr(char p,char* E1,char* E2)

{ BinaryTreeAndExpr BTAE1,BTAE2,*BTAE3; BTAE1.ReadExpr(E1); BTAE2.ReadExpr(E2); TreeNode* q=(TreeNode*)new TreeNode(p,NULL,NULL); q->SetLeft(BTAE1.GetRoot()); q->SetRight(BTAE2.GetRoot()); BTAE3=(BinaryTreeAndExpr*)new BinaryTreeAndExpr; BTAE3->SetRoot(q); return BTAE3; } void BinaryTreeAndExpr::SetRoot(TreeNode* _root) { root=_root; } int BinaryTreeAndExpr::Value(char* E) { BinaryTreeAndExpr btae; btae.ReadExpr(E); return btae.ValueRecursion(btae.GetRoot()); } int BinaryTreeAndExpr::ValueRecursion(TreeNode* p) { char c1,c2; int temp1,temp2; if(p->GetLeft()==NULL || p->GetRight()==NULL) { c1=p->GetData(); return (c1>=97 && c1<=122)?0:c1-48; } c1=p->GetLeft()->GetData(); c2=p->GetRight()->GetData(); if(!IsOperator(c1) && !IsOperator(c2)) { if(c1>=97 && c1<=122) temp1=0; else temp1=c1-48; if(c2>=97 && c2<=122) temp2=0; else temp2=c2-48; return Evaluation(temp1,p->GetData(),temp2); } else if(IsOperator(c1) && !IsOperator(c2))

{ temp1=ValueRecursion(p->GetLeft()); if(c2>=97 && c2<=122) temp2=0; else temp2=c2-48; return Evaluation(temp1,p->GetData(),temp2); } else if(!IsOperator(c1) && IsOperator(c2)) { temp2=ValueRecursion(p->GetRight()); if(c1>=97 && c1<=122) temp1=0; else temp1=c1-48; return Evaluation(temp1,p->GetData(),temp2); } else { temp1=ValueRecursion(p->GetLeft()); temp2=ValueRecursion(p->GetRight()); return Evaluation(temp1,p->GetData(),temp2); } } int BinaryTreeAndExpr::Evaluation(int a,char op,int b) { switch(op) { case '+': return a+b; break; case '-': return a-b; break; case '*': return a*b; break; case '/': return a/b; break; case '^': return pow(a,b); break; }

return 0; } 3、ExpressionMain.cpp 文件的实现 #include<iostream> #include"Expression.h" using namespace std; int main() { BinaryTreeAndExpr btae,*btae1; char E1[100],E2[100],P,V; int switchs,c,switchs2; bool run=true,run2=true; while(run) { cout<<"请选择功能,功能如下:"<<endl; cout<<"1.构造复合表达试并输出相应结果."<<endl; cout<<"2.输入前缀表达试并构造中缀表达试."<<endl; cout<<"3.对前缀表达试求值."<<endl; cout<<"4.退出."<<endl; cin>>switchs; switch(switchs) { case 4: run=false; break; case 1: cout<<"请输入相关数据.前缀表达试"<<endl; getchar(); scanf("%s %c %s",E1,&P,E2); btae1=BinaryTreeAndExpr::CompoundExpr(P,E1,E2); while(run2) { cout<<"如有变量要赋值请输入 1，否则输入 2"<<endl; cin>>switchs2; if(switchs2==1) { cout<<"请输入相关数据."<<endl; getchar(); scanf("%c %d",&V,&c); btae1->Assign(V,c);

} else run2=false; } btae1->WriteExpr(E1); cout<<"中缀表达试:"<<E1<<endl; btae1->Release(); delete(btae1); run2=true; break; case 2: cout<<"请输入相关数据.前缀表达试"<<endl; cin>>E1; btae.ReadExpr(E1); while(run2) { cout<<"如有变量要赋值请输入 1，否则输入 2"<<endl; cin>>switchs2; if(switchs2==1) { cout<<"请输入相关数据."<<endl; getchar(); scanf("%c %d",&V,&c); btae.Assign(V,c); } else run2=false; } cout<<"中缀表达试:"; btae.WriteExpr(E2); cout<<E2<<endl; run2=true; break; case 3: cout<<"请输入相关数据.前缀表达试"<<endl; cin>>E1; btae.ReadExpr(E1); btae.WriteExpr(E2); cout<<"中缀表达试为:"; cout<<E2<<endl; cout<<"计算结果为:"; cout<<BinaryTreeAndExpr::Value(E1)<<endl; break;

default: cout<<"你的输入无效!请重新输入."<<endl; break; } btae.Release(); if(run) cout<<endl; } return 0; } 四、 调式分析： 1、 调式时递归函数不正确，出现一些逻辑错误，经改正后最终得到了正确的结果。 2、 体会，学会了二叉树的使用。 五、 用户使用说明： 按相关提示输入，即可得到结果。 六、 测试结果: 见下页：

<<数据结构>> 课程设计 表达式类型的实现 2008 年 7 月 3 日 数据结构课程设计报告 一、需求分析【课程设计要求】 【问题的描述】 一个表达式和一棵二叉树...

...-数据结构课程设计表达式类型的实现(难度系数1.2).doc

《数据结构与算法》上的一道作业题答案,本程序设计二叉树的构建,遍历以及打印等函数,能够实现自动分辨所输入表达式属于什么类型。// TheRealBinaryTreeOfMine.cpp :...

(003)(课程设计报告)(10065012)(舒焕).doc
(003)(课程设计报告)(10065012)(舒焕) - 《数据结构》课程设计 表达式类型的实现 一 目的 熟练掌握《数据结构》课程的相关知识,完成一个具有一定难度的综合设计...