您的位置： >
来源：　　作者：陈海珠;郑卉;
基于二叉树的算术表达式计算与实现　 1概述数学表达式求值是程序设计语言编译中的一个最基本问题。表达式的求值是栈应用的一个典型例子。表达式前缀、中缀、后缀三种形式,相应的也就有前缀、中缀(普通计算器)、后缀三种计算器。数据结构教材使用二叉树表示一个算术表达式,前序、中序、后序遍历该二叉树分别得到前缀、中缀、后缀表达式,再把这些表达式用堆栈来实现不同的计算器。如何由算术表达式得到其二叉树表示,在数据结构的教材上鲜有提及,而在所发表的论文中对此问题的解决办法通常是采用堆栈作为辅助的存储结构来实现算术表达式向二叉树的转换。本文不使用堆栈,采用递归编程的方式来实现表达式向二叉树的转换,然后通过先序遍历该二叉树来求出表达式的值。采用这样的方式来构建二叉树更简便而有效,由于不需要转换成某种表达式也不需要使用堆栈,本文的方法可以直接地求出表达式的值。为方便讨论,我们将由表达式转换成的二叉树称为表达式树。2表达式树的构建首先我们来观察二叉树如何来描述一个表达式。如图1所示,表达式树的结点存储操作数和二元操作符(+、-、*、/)。由此可看出,二叉树是存储算术表达式的最佳数据结构,原因在于只要以不同顺序遍历此树就能够生成表达式的不同表示。表达(本文共计2页)　　　　　　　　　　
相关文章推荐
看看这些杂志对你有没有帮助...
单期定价：32.00元/期全年定价：25.60元/期　共614.40元
　　　　　　一种字符串表达式求值的简单方法
我的图书馆
一种字符串表达式求值的简单方法
在程序设计过程中，可能碰到需要对字符串型数学表达式进行求值，通用且完美的方法是将字符串表达解析，生成表达树，然后进行计算。编译器就是使用这种方法来解析程序中的表达式的。这种方法实现起来有点难度，需要考虑运算符的优先级，括号的配对，堆栈的使用等等。
我们正常情况下看到的数学表达式如果用二叉树遍历的话，恰好是中序遍历，故叫做中序表达式。除此之外，还有前序表达式，后序表达式。如：a+b+c(中序)，++abc(前序)，ab+c+(后序)，如果表达式含有×，／，（）等就更复杂了。
既然使用生成表达式树的方法直接执行通常的中序表达式有点困难，那就考虑一下其它的两个表达式吧。这里介绍如何用后序表达式来求值，这种方法早在以前就有人介绍了，因为其简单，易实现，故偶在这里重新阐述一下。
后缀表达式——将运算符放在两操作数的后面。后缀表达式也称逆波兰表达式 因其使表达式求值变得轻松，所以被普遍使用。
前缀和后缀表示法有三项公共特征：
1.操作数的顺序与等价的中缀表达式中操作数的顺序一致
2.不需要括号
3.操作符的优先级不相关
当然我们不可能自己特意去写一个后序表达式，这样很难受，因为我们早就习惯了中序表达式这种形式，因此我们需要将中序表达首先转化为后序表达式，去掉括号。中缀转后缀是栈应用的一个典型例子。其转换方法采用运算符优先法。转换过程需借助一个运算符栈和一个存放逆波兰表达式的数组。
转换方法如下：
1.将表达式开始符“＃”压入运算符栈，作为栈底元素。
2.读入操作数，直接存入数组。
3.读入运算符，压入运算符栈。
若后进运算符优先级别高于当前栈顶元素时，则继续进栈；
若后进运算符优先级别低于或等于当前栈顶元素时，则将当前栈顶元素出栈，存入数组后进运算符入栈。
4.括号处理
遇到开括号"（"，将括号进运算符栈；遇到闭括号"）"，则把最靠近的开括号，以及该开括号其遇到闭括号，后进栈的运算符依次出栈，存入数组（括号脱去）
5.遇到表达式结束符则把运算符栈内的所有运算符依次弹出，并存入数组。
后缀表达式的执行：
1.先读入两个操作数，遇到操作符，则将这两个操作数进行该操作符对应的计算。
2.保存计算结果，并将其作为下一个操作的第一个操作数。
3.读入下一个操作数，如果已到表达式结尾（即读到空），则算法结束，否则进行第4步
4.读入下一个操作符，进行对应的计算。转第2步。
上面的方法可以使用任意程序设计语言来实现。这里提供一个C#实现的类，该类利用了C#语言特有的一些性质，可以对任意的表达式求值，并且能够解析字符串形式的代码。类代码如下 ：
using Susing System.CodeDusingusing Microsoft.CSusing System.Tusing System.Rnamespace ADOGuy...{ /**//// &summary& /// 此类用于C#计算字符串表达式语句，能计算的语句包括所有的数学表达式： /// 简单加减乘除表达式：如1+2+2,1*5+1等， /// 有数学函数的复杂表达：如1+Math.Cos(1)，Math.Sqrt(20)等 /// 注意，方法的调用应与表达式的返回结果相对应，否则出错 /// &/summary& public class Evaluator ...{ Construction#region Construction public Evaluator(EvaluatorItem[] items) ...{ ConstructEvaluator(items); } public Evaluator(Type returnType, string expression, string name) ...{ EvaluatorItem[] items = ...{ new EvaluatorItem(returnType, expression, name) }; ConstructEvaluator(items); } public Evaluator(string varDefineCode, Type returnType, string expression, string name) ...{ EvaluatorItem[] items = ...{ new EvaluatorItem(varDefineCode, returnType, expression, name) }; ConstructEvaluator(items); } public Evaluator(EvaluatorVarDefineItem subItem, Type returnType, string expression, string name) ...{ EvaluatorItem[] items = ...{ new EvaluatorItem(subItem, returnType, expression, name) }; ConstructEvaluator(items); } public Evaluator(EvaluatorItem item) ...{ EvaluatorItem[] items = ...{ item }; ConstructEvaluator(items); } private void ConstructEvaluator(EvaluatorItem[] items) ...{ ICodeCompiler comp = (new CSharpCodeProvider().CreateCompiler());//有警告，可以试试下一句 //CodeDomProvider comp = new CSharpCodeProvider(); CompilerParameters cp = new CompilerParameters(); cp.ReferencedAssemblies.Add("system.dll"); cp.ReferencedAssemblies.Add("system.data.dll"); cp.ReferencedAssemblies.Add("system.xml.dll"); cp.GenerateExecutable = false; cp.GenerateInMemory = true; StringBuilder code = new StringBuilder();//将要编译的代码串写入code code.Append("using S "); code.Append("namespace ADOGuy { "); code.Append(" public class _Evaluator { "); foreach (EvaluatorItem item in items) ...{ code.AppendFormat(" public {0} {1}() ", item.ReturnType.Name, item.Name); code.Append("{ "); code.Append(item.VarDefineCode + " "); code.AppendFormat(" return ({0}); ", item.Expression); code.Append("} "); } code.Append("} }"); Console.WriteLine(code); CompilerResults cr = pileAssemblyFromSource(cp, code.ToString());//从code串构建程序 if (cr.Errors.HasErrors) ...{ StringBuilder error = new StringBuilder(); error.Append("Error Compiling Expression: "); foreach (CompilerError err in cr.Errors) ...{ error.AppendFormat("{0} ", err.ErrorText); } throw new Exception("Error Compiling Expression: " + error.ToString()); } Assembly a = cr.CompiledA _Compiled = a.CreateInstance("ADOGuy._Evaluator");//创建程序实例 } #endregion Public Members#region Public Members public int EvaluateInt(string name) ...{ return Convert.ToInt32(Evaluate(name)); } public string EvaluateString(string name) ...{ return Convert.ToString(Evaluate(name)); } public bool EvaluateBool(string name) ...{ return Convert.ToBoolean(Evaluate(name)); } public float EvaluateFloat(string name) ...{ return Convert.ToSingle(Evaluate(name)); } public double EvaluateDouble(string name) ...{ return Convert.ToDouble(Evaluate(name)); } public object EvaluateObject(string name) ...{ return Evaluate(name); } public object Evaluate(string name) ...{ MethodInfo mi = _Compiled.GetType().GetMethod(name);//利用实例调用由name指定的方法进行计算 return mi.Invoke(_Compiled, null); } #endregion Static Members#region Static Members static public int EvaluateToInteger(string code) ...{ Evaluator eval = new Evaluator(typeof(int), code, staticMethodName); return Convert.ToInt32(eval.Evaluate(staticMethodName)); } static public string EvaluateToString(string code) ...{ Evaluator eval = new Evaluator(typeof(string), code, staticMethodName); return Convert.ToString(eval.Evaluate(staticMethodName)); } static public bool EvaluateToBool(string code) ...{ Evaluator eval = new Evaluator(typeof(bool), code, staticMethodName); return Convert.ToBoolean(eval.Evaluate(staticMethodName)); } static public double EvaluateToDouble(string code) ...{ Evaluator eval = new Evaluator(typeof(double), code, staticMethodName); return Convert.ToDouble(eval.Evaluate(staticMethodName)); } static public object EvaluateToObject(string code) ...{ Evaluator eval = new Evaluator(typeof(object), code, staticMethodName); return eval.Evaluate(staticMethodName); } static public int EvaluateToInteger(string varDefineCode, string code) ...{ Evaluator eval = new Evaluator(varDefineCode, typeof(int), code, staticMethodName); return Convert.ToInt32(eval.Evaluate(staticMethodName)); } static public string EvaluateToString(string varDefineCode, string code) ...{ Evaluator eval = new Evaluator(varDefineCode, typeof(string), code, staticMethodName); return Convert.ToString(eval.Evaluate(staticMethodName)); } static public bool EvaluateToBool(string varDefineCode, string code) ...{ Evaluator eval = new Evaluator(varDefineCode, typeof(bool), code, staticMethodName); return Convert.ToBoolean(eval.Evaluate(staticMethodName)); } static public double EvaluateToDouble(string varDefineCode, string code) ...{ Evaluator eval = new Evaluator(varDefineCode, typeof(double), code, staticMethodName); return Convert.ToDouble(eval.Evaluate(staticMethodName)); } static public object EvaluateToObject(string varDefineCode, string code) ...{ Evaluator eval = new Evaluator(varDefineCode, typeof(object), code, staticMethodName); return eval.Evaluate(staticMethodName); } #endregion Private#region Private const string staticMethodName = "__foo"; Type _CompiledType = null; object _Compiled = null; #endregion } ...#region public class EvaluatorItem ...{ public EvaluatorItem(Type returnType, string expression, string name) ...{ ReturnType = returnT Expression = Name = } public EvaluatorItem(string varDefineCode, Type returnType, string expression, string name) ...{ VarDefineCode = varDefineC ReturnType = returnT Expression = Name = } public EvaluatorItem(EvaluatorVarDefineItem subItem, Type returnType, string expression, string name) ...{ VarDefineCode = subItem.getVarDefineCode(); ReturnType = returnT Expression = Name = } public string VarDefineCode = ""; public Type ReturnT public string N public string E } #endregion ...#region public class EvaluatorVarDefineItem ...{ private string VarDefineCode = ""; public EvaluatorVarDefineItem()...{} public EvaluatorVarDefineItem(Type varType, string varName, string varValue) ...{ this.VarDefineCode = varType.Name + " " + varName.Trim() + " = " + varValue.Trim() + ";"; } public EvaluatorVarDefineItem(Type varType, string varExpression) ...{ this.VarDefineCode = varType.Name + " " + varExpression + ";"; } public string getVarDefineCode() ...{ return this.VarDefineC } public void addVarExpression(Type varType, string varName, string varValue) ...{ this.VarDefineCode += " "+varType.Name + " " + varName.Trim() + " = " + varValue.Trim() + ";"; } public void addVarExpression(Type varType, string varExpression) ...{ this.VarDefineCode += " " + varType.Name + " " + varExpression + ";"; } }; #endregion}
发表评论：
TA的最新馆藏下载作业帮安装包
扫二维码下载作业帮
1.75亿学生的选择
如何将一个表达式转换成二叉树理解表达式a*（b+c）-d的后缀表达式,这个怎么画出二叉树?
表达式生成树的特点为:&&&&a. 叶子节点都是操作数；& & b. 非叶子节点都是运算符；& & c. 树根的运算符优先级低；步骤如下找到表达式中优先级最低的运算符作为树根（注意括号会提升内部的优先级）,并将原表达式分解成左右两个表达式;分别对左右表达式做步骤1, 左边生成的树为树根的左子树,右边生成的树为树根的右子树；重复步骤1,2, 直到分解的表达式里没有运算符（只剩下数字）为止；
为您推荐：
其他类似问题
扫描下载二维码表达式与二叉树的相互转换
1概述数学表达式求值是程序设计语言编译中的一个最基本问题。因此,数学表达式、栈的操作、二叉树的遍历,这几个概念在数据结构的教材中往往经常出现。表达式的求值过程是栈应用的一个典型例子,用它来研制出电子计算器:当用户输入一个由数据(操作数)和运算符组成的算术表达式,计算器使用一个堆栈来计算运算结果。当然表达式也有几种形式:前缀表达式、中缀表达式、后缀表达式。因此,又出现了前缀计算器、中缀计算器(常见的计算器)、后缀计算器。对于中缀表达式就是我们常用的数学表达式中去掉括号的部分表达式,是经常可看见的;但是,前缀表达式和后缀表达式是怎么得出来的呢我们的数据结构教材中是将一个数学表达式或者中缀表达式以及其所表示的二叉树,对该二叉树的前序遍历得到前缀表达式,对该二叉树的中序遍历就得到中缀表达式,对该二叉树的后序遍历就得到后缀表达式,再根据这些表达式用堆栈来实现,以得到不同的计算器。也就是说,教材中所阐述的过程是这样的:数学表达式(中缀表达式...&
(本文共3页)
权威出处：
0引言二叉树的逻辑结构为树型结构,结点间是一对多的层次关系。所谓二叉树的遍历是指按一定规律对二叉树中每个结点进行访问且仅访问一次[1-2]。“访问”的含义很广,可以是对结点作各种处理,如输出结点的信息等[2,3]。二叉树的遍历是二叉树中所有其他运算的基础。本文介绍了二叉树遍历在搜索二叉树中最长路径算法中的应用,重点分析算法的设计过程,并给出算法的C语言描述。1二叉树的存储结构首先考虑二叉树的存储结构。接近完全二叉树形态的二叉树采用静态向量的存储方式比较好,此时结点的父子关系可根据完全二叉树的性质5[2-5](对一棵有n个结点的完全二叉树的结点按层序从1开始编号,则对任一序号大于1的结点i,其双亲结点序号为[i/2],若其左孩子序号小于n,则为2i,若其右孩子序号小于n,则为2i+1)定位对应的下标结点,其存储结构可用C语言定义如下[1]:#define MAX 1000typedef struct{DataType data[M...&
(本文共3页)
权威出处：
目前,我国的海运事业进入了空前的发展时期,安全、经济的海上航行变得日益重要[1-2]。军事上,面对复杂多变的航行环境,自动、快速地设计合理的航线,可赢得战机,为胜利创造条件[3-4]。因此,进行高质量的电子海图航线设计在民用和军事上都有重要意义。文献[4-5]等利用基于已知航路点库的航线网络方法进行了最佳航线的选择方法研究,但实际上并不是任何海区事先都建有非常合理的航路点库,同时也并非只有这些航路点之间可以航行。在军事上,需要根据作战任务需求,灵活快速地确定合理的海上航线。因此,基于电子海图,自动搜索海上任意两点之间的最短路径成为一个具有现实意义的问题。陈传波等利用所要绕行的碍航区的顶点与测试线(当前点与目的点的连线)距离最小原则,构建了自动绕行碍航区机制[6]。张立华提出了电子海图平台下最优航线的自动生成算法[7],利用方位相差最小和航段最大等准则,建立了自动绕行碍航区的机制,考虑到了绕行碍航区时存在左右两条路径的问题。为了提...&
(本文共4页)
权威出处：
0引言在计算机领域中,树型结构是一类非常重要的非线性结构,其中二叉树最为常用,对二叉树的操作和存储比树相对简单。二叉树的存储一般采用顺序存储和链式存储。顺序存储是将一棵二叉树的结点存放于一组地址连续的存储单元中,这种存储结构对完全二叉树而言,既简单又节省存储空间。但对于一般二叉树,尤其对于单支结点较多的二叉树很不适合,由于对其存储也必须按完全二叉树的形式存储二叉树中的结点,从而造成存储空间的浪费。因此,二叉树一般采用链式存储结构。二叉树的链式存储结构分为两种,一种是动态链式存储,另一种是静态链式存储。二叉树的动态链式存储是采用链表的形式存储二叉树,一般采用二叉链表和三叉链表。二叉树的静态存储是用一个数组存储二叉树的各个结点,数组中不仅保存每个结点的信息,还存储该结点左、右孩子在数组中的地址信息。下面分别对二叉树的动态链式存储和静态链式存储进行分析研究。1二叉树的动态链式存储二叉树的动态链式存储有两种形式,一是二叉链表,即链表中每...&
(本文共4页)
权威出处：
二叉树是《图论》、《离散数学》等学科中的一个重要内容,二叉树作为一种存储结构,在计算机中操作和实现都非常方便,在计算机科学中有着重要的作用,所以由二叉树的遍历序列反过来求它们所表示的二叉树是十分必要的[1]。在包括文献[1]的很多文献中都说明不能由二叉树的先序序列和后序序列唯一恢复一棵二叉树,其实在一定条件下这两种遍历序列也是可以唯一恢复一棵二叉树的。1二叉树的定义二叉树由结点的有限集合构成,该集合或者为空集,或者由一个根结点及两棵互不相交的分别称为根的左子树和右子树的二叉树组成[2]。集合可以描述为T,TL,TR;分别代表根结点,左子树和右子树;其中左子树或右子树可以为空。故有三种形态。图1 T有左右子树图2 T只有左子树图3 T只有右子树第24卷第3期先序和后序序列恢复二叉树的非递归算法结点的度每个结点的左右孩子个数称为该结点的度,度的值可以为0,1或2。2.1含度为1的结点所要恢复的二叉树中含有度为1的结点...&
(本文共3页)
权威出处：
0引言所有结点的度不是0就是2的非空二叉树称为严格二叉树.人们已经提出了一些由一棵二叉树的先序和中序序列、中序和后序序列、中序和层序序列、中序序列和结点的双亲情况、中序序列和结点的左孩子情况、后序序列和结点的左孩子情况、先序序列和结点的右孩子情况、中序序列和结点的右孩子情况以及中序序列和结点的层数构造该二叉树的算法,如文献[1-2].这些算法当然适用于严格二叉树.根据基于遍历序列的唯一确定严格二叉树的方法,本文提出一些新的基于遍历序列的构造严格二叉树的算法.1算法可以证明严格二叉树的结点的个数是正奇数.由一棵严格二叉树的先序和后序序列可以唯一确定该严格二叉树[3].若一棵严格二叉树的先序和后序序列都只有一个结点,则该严格二叉树只有该结点.否则,设a1,a2,…,an和c1,c2,…,cn分别是该严格二叉树的先序和后序序列(n是大于或等于3的奇数).a1和cn都是根.左子树和右子树也是严格二叉树.a2是左子树的根,在c1,c2,…...&
(本文共5页)
权威出处：
扩展阅读：
CNKI手机学问
有学问，才够权威！
出版：《中国学术期刊（光盘版）》电子杂志社有限公司
地址：北京清华大学 84-48信箱 大众知识服务
互联网出版许可证 新出网证(京)字008号
京ICP证040431号
服务咨询：400-810--9993
订购咨询：400-819-9993
传真：010-}