当前位置:首页 >> 计算机软件及应用 >>

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


表达式 1 / 14

表达式类型的实现
一、 需求分析: 1、 输入时按相关提示进行输入。 2、 输出的形式,输出时按相关功能进行输出。 3、 功能,实现前缀表达式转换为中缀表达式,并进行相应的求值和赋值运算,与及构 造复合表达式。 4、 测试数据,见输出结果。 二、 概要设计: 实现该程序所要用到的函数:

三、 详细设计: 见源码: 1、Expression.h 文件的实现 #ifndef _EXPRESSION_H_ #define _EXPRESSION_H_ //-------------------树节点类 class TreeNode { public: TreeNode(char _data,TreeNode* _left,TreeNode* _right); ~TreeNode(); char GetData();

表达式 2 / 14

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>

表达式 3 / 14

#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; }

表达式 4 / 14

//---------------------------- 二叉树几及表达式类成员函数 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; }

表达式 5 / 14

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();

表达式 6 / 14

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'; } }

表达式 7 / 14

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 '*':

表达式 8 / 14

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)

表达式 9 / 14

{ 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))

表达式 10 / 14

{ 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; }

表达式 11 / 14

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);

表达式 12 / 14

} 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;

表达式 13 / 14

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

表达式 14 / 14


相关文章:
实验六 二叉树实验报告(1)
二叉树对于进行表达式的前缀,中缀和后缀的表示有明显的优势,既方便, 又容易理解...typedef struct Node //创建结点类型结构体 { DataType data; struct Node *LChi...
2012江苏省计算机等级考试试题 二级C试题试题及答案
按条件 f 对关系 R 进行选择,其关系代数表达式为(...二叉树是线性结构 22、数据的存储结构是指(B) A....数据库系统中数据的一致性是指数据类型的一致 D. ...
更多相关标签: