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

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


表达式 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


相关文章:
表达式类型的实现(二叉树).doc
表达式类型的实现(二叉树) 用二叉树实现前缀表达式转换为中缀表达式,并对其计算,
表达式类型的实现.doc
另外,通过中序遍历二叉树表达式进行化简。 2.基本功能 ⑴以字符序列的形式输入语法正确的前缀表示式并构成表达式E ⑵用带括号的中缀表达式输出表达式E ⑶实现对...
课程设计报告-表达式类型的实现.doc
<<数据结构>> 课程设计 表达式类型的实现 2008 年 7 月 3 日 数据结构课程设计报告 一、需求分析【课程设计要求】 【问题的描述】 一个表达式和一棵二叉树...
数据结构课程设计-表达式类型的实现(难度系数_1.2).doc
数据结构课程设计-表达式类型的实现(难度系数_1.2) - 数据结构课程设计报告 题目:表达式类型的实现(难度系数:1.2) 学专 院业 计算机 计算机科学与技术 2015 级...
达式类型的实现.doc
达式类型的实现 - **理工大学 数据结构课程设计报告 题目: 表达式类型的实现 院(系): 学生姓名: 班级: 计算111 计算机工程学院 ** 学号: 2011070** 起迄...
...-数据结构课程设计表达式类型的实现(难度系数1.2).doc
本科毕业设计论文--数据结构课程设计表达式类型的实现(难度系数1.2)_远程、网络...二、【概要设计】 1、数据类型的声明: 在这个课程设计中,采用了链表二叉树的...
数据结构课设_图文.ppt
数据结构课设 - 数据结构课程设计-基于二叉树的表达式运算... 数据结构课程设计表达式类型的实现 问题描述一个表达式和一棵二叉树之间,存在着自然的 对应关系。写一个...
数据结构实验报告.doc
数据结构实验报告 - 课程设计实验报告 实验名称:表达式类型的实现 编译环境:硬件:PC 软件:VS2010 问题描述 一个表达式和一棵二叉树之间,存在着自然的对应关系。写...
表达式构建二叉树(中缀,前缀,后缀).doc
《数据结构与算法》上的一道作业题答案,本程序设计二叉树的构建,遍历以及打印等函数,能够实现自动分辨所输入表达式属于什么类型。// TheRealBinaryTreeOfMine.cpp :...
数据结构课程设计表达式的实现&图的遍历.doc
数据结构课程设计题目一:表达式类型的实现 题目二:图的遍历 表达式类型的实现 一、需求分析 1.【问题的描述】一个表达式和一棵二叉树之间,存在着自然的对应关系。...
后序遍历二叉树实现表达式求值_论文.pdf
后序遍历二叉树实现表达式求值_数学_自然科学_专业资料。山西师 范大学学报 ( ...的类 型等 , 具有 一定 的实用价值 . 关键词 :中缀表达式 ; 后序遍历 ;...
任务书算术表达式与二叉树.doc
课程设计题目 算术表达式与二叉树 二、课程设计内容(含技术指标) 【问题描述】 ...二叉树表示表达式11 4页 1下载券 表达式类型的实现(二叉树... 14页 2下载...
数据结构-二叉树类型的实现.doc
实验4 表达式二叉树类型的实现 源代码及每步注解:文件 expression.h
表达式二叉树上机报告.doc
表达式二叉树上机报告班级:11070227 姓名:周潇 学号:11070227 完成日期:2013.4....(1)请输入表达式类型,前缀表达式输入-1,中缀表达式输入 0,后缀表达式输入 1. ...
表达式求值 C++代码 实验报告.doc
实验项目名称_树结构的应用:表达式类型的实现_ 指导教师及职称_ 尹爱华 开课...{ 定义输入变量 用户输入二叉树前缀表达式,#代表结束输入 读入字符 while(ch!=...
数据结构课程设计报告.doc
数据结构课程设计报告 - <<数据结构>> 课程设计报告 题 目 5.7 表达式类型的实现 200 8 年 7 月 表达式类型的实现 一、存储结构定义 本程序在关于二叉树...
表达式二叉树.doc
表达式二叉树 - 对于任意给出的前缀表达式(不带括号)、中缀表达式(可以带括号)或后缀表达式(不带括号),能够在计算机内部构造出一棵表达式二叉树,并且图示出来(图形...
课程设计.doc
课程设计 - 数据结构课程设计报告 题目:表达式类型的实现(难度系数:1.2)
(003)(课程设计报告)(10065012)(舒焕).doc
(003)(课程设计报告)(10065012)(舒焕) - 《数据结构》课程设计 表达式类型的实现 一 目的 熟练掌握《数据结构》课程的相关知识,完成一个具有一定难度的综合设计...
表达式与二叉树的相互转换_图文.pdf
用它来研和1出各种类型的电子计算器(前缀计算器、中缀计算器(常见的计算 器)...的二叉树二叉树的遍历,前缀表达式、中缀表达式、后缀表达式一栈的实现一前缀...
更多相关标签: