数据结构中的数学表达

数据结构中的数学表达

1数学式的实现数学句子的计算是语言编译中最基本的问题。因此,数学表达式、栈的操作、二叉树的遍历,这几个概念在数据结构的教材中往往经常出现。表达式的求值过程是栈应用的一个典型例子,用它来研制出电子计算器:当用户输入一个由数据(操作数)和运算符组成的算术表达式,计算器使用一个堆栈来计算运算结果。当然表达式也有几种形式:前缀表达式、中缀表达式、后缀表达式。因此,又出现了前缀计算器、中缀计算器(常见的计算器)、后缀计算器。对于中缀表达式就是我们常用的数学表达式中去掉括号的部分表达式,是经常可看见的;但是,前缀表达式和后缀表达式是怎么得出来的呢?我们的数据结构教材中是将一个数学表达式或者中缀表达式以及其所表示的二叉树,对该二叉树的前序遍历得到前缀表达式,对该二叉树的中序遍历就得到中缀表达式,对该二叉树的后序遍历就得到后缀表达式,再根据这些表达式用堆栈来实现,以得到不同的计算器。也就是说,教材中所阐述的过程是这样的:数学表达式(中缀表达式)+该表达式的二叉树→二叉树的遍历→前缀表达式、中缀表达式、后缀表达式→栈的实现→前缀计算器、普通计算器、后缀计算器。用图形表示其过程如下:初看起来显然是比较合理的,但是我们的教材上从来没有提到过怎样得到该“数学表达式”的“二叉树”。本文正想阐明怎样由一个“表达式”得出其相应的“二叉树”。2相关术语2.1装饰公式就是运算符(操作符)在两个运算对象(操作数)中间的表达式。如:A+B,C*D-E。2.2两个运算对象操作数之前的算子就是在一个数学表达式中,运算符(操作符)在两个运算对象(操作数)之前的表达式。如:+AB,-*CDE。前缀表达式又称波兰式(PN,PolishNotation)。2.3运算对象之后的公式就是在一个数学表达式中,运算符(操作符)在两个运算对象(操作数)之后的表达式。如:AB+,CD*E-。后缀表达式又称逆波兰式(RPN,ReversePolishNotation)。2.4配置树就是将一个数学表达式用一棵二叉树表示。其中,运算对象作为树的叶子结点(没有后继的结点),运算符作为树的非叶子结点。如图1,图2所示。2.5中回收式pn1)先根(先序)遍历:先遍历根结点,再先根遍历左子树,再先根遍右子树。对于上面的图1、图2分别为:+AB,-*CDE。得到相应表达式的前缀表达式(波兰式(PN,PolishNotation))。2)中根(中序)遍历:先中根遍历左子树,访问根结点,中根遍历右子树。对于上面的图1、图2分别为:A+B,C*D-E。得到相应表达式的中缀表达式。3)后根(后序)遍历:先后根遍历左子树,再后根遍历右子树,最后访问根结点。对于上面的图1、图2分别为:AB-,CD*E-。得到相应表达式的后缀表达式(逆波兰式(RPN,ReversePolishNotation))。3构造二叉树的根将数学表达式表示为表达式树,关键问题是:最后进行运算的运算符作为二叉树(表达式树)的树根,以该运算符作为界线,在其前面的部分(这里称子表达式1)为二叉树的左子树的表达式,在运算符后面的部分(这里称子表达式2)为右子树的表达式,再分别对子表达式1、子表达式2递归使用以上规则构建左、右子树。例如:将表达式:((a+b)+c*(d+e)+f)*(g+h)表示成表达树。其构造过程如下:首先,先确定二叉的根。根据数学运算顺序知:“g”前面的“*”是最后运算的运算符,因此该“*”作为二叉树的树根如图3。子表达式1为:(a+b)+c*(d+e)+f;子表达式2为:g+h。分别递归构造左、右子树。其次,构造二叉树的左子树。根据子表达式1:(a+b)+c*(d+e)+f,分析知:f前的“+”为整个左子树的树根,f为左子树的右子树。再分析其左子树部分:(a+b)+c*(d+e)如图5。子表达式1:(a+b)+c*(d+e)+f所构成的左子树为图6。再次,构造二叉树的右子树。由子表达式2:g+h,分析知:右子树的根为:“+”,右子树的左叶子为“g”,而右叶子为:“h”。从而得如图7。根据图3、图6和图7。得出表达式:((a+b)+c*(d+e)+f)*(g+h)的表达式树为图8。对图8的前根遍历得:*+++ab*c+bef+gh.。即表达式:((a+b)+c*(d+e)+f)*(g+h)的前缀表达式(波兰式)为:*+++ab*c+bef+gh.。对图8的中根遍历得:a+b+c*d+e+f*g+h。即表达式:((a+b)+c*(d+e)+f)*(g+h)的中缀表达式为:a+b+c*d+e+f*g+h。对图8的后根遍历得:ab+cde+*+f+gh+*。即表达式:((a+b)+c*(d+e)+f)*(g+h)的后缀表达式(逆波兰式)为:ab+cbe+*+f+gh+*。4左、右子树的样式由于前缀算术表达式(波兰式)的运算符(操作符)在两个操作数(操作对象)之前,非叶子结点全为运算符。因此,可按如下规则进行构造二叉树(表达式树):第一个运算符作为二叉树的树根;紧接着选择其后第一次满足运算符个数比操作数个数少1的部分表达式作为左子树的表达式;剩下的部分表达式为右子树的表达式。再分别对分出的两表达式递归使用以上规划。例2:写出前缀表达式:-*a^b-+c*defg的表达式树。解题过程如下:第一个“-”为树根:如图9。根据以上规则:左子树部的表达式为:*a^b-+c*def;右子树部分的表达式为:g。构造左子树:左子树树根为:“*”,“*”的左子树为“a”如图9;右子树表达式为:^b-+c*def。递归构造可得如图10。将图10、图11组合得左子树为:图12。再由图9、图12以及右子树“g”得“-*a^b-+c*defg”的表达式树为图13。对该树后序遍历可得后缀表达式(逆波兰式):abcde*+f-^*g-。同样对该树中序遍历可得中缀表达式:a*b^c+d*e-f-g。当然真正的数学表达式为:a*(b^((c+d*e)-f))-g图115构造式的后1化由于后缀算术表达式(逆波兰式)的运算符(操作符)在两个操作数(操作对象)之后,非叶子结点全为运算符。因此,可按如下规则进行构造二叉树:最后一个运算符作为二叉树的树根;紧接着从后往前选择第一次满足运算符个数比操作数个数少1的部分表达式作为右子树部分的表达式;剩下的部分表达式为左子树的表达式。再分别对两表达式递归使用以上规划;对于简单表达式(一个运算符,两个运算对象)从后往前分别是:根、右孩子、左孩子的顺序构造。例3:用后缀表达式:ab+cde+*+f+gh+*构造表达式树,并求出其前缀和中缀表达式。解:第一步:根据以上规则:最后一个“*”为树根;如图14。“gh+”为表达式树的右子树部分的表达式;“ab+cde+*+f+”为表达式树左子树部分的表达式。第二步:右子树为:根为:“+”;右孩子为:“h”;左孩子为:“g”;如图15。第三步:左子树为:根为:“+”;右子树为:“f”如图16,其左子树的表达式为:“ab+cde+*+”;再对“ab+cde+*+”构造子二叉树。由上规则得:该子二叉树的根为:“+”,右子树部分的表达式为:“cde+*”;左子树部分的表达式为:“ab+”,即如右图17。综合上面四个图,表达式“ab+cde+*+f+gh+*”的二叉树为如图18所示。因此,对该二叉树的前序遍历可得波兰式:*+++ab*c+def+gh.。对该二叉树中序遍历可得中缀表达式:a+b+c*d+e+f*g+h.。当然真正的数学表达式为:(a+b+c*(d+e)+f)*(g+h)。6生成三种不同的处理器运用该文中所介绍的三种表达式与二叉树的转换规则,能顺利地由一种表达式将其转化为二叉树(表达式树),再对该二叉树(表达式树)的遍历,可得到其他的