基于二叉树的将中缀表达式转换为前缀表达式的方法

2012-01-10胡云

成都大学学报（自然科学版） 2012年3期

胡云

(无锡广播电视大学,江苏无锡 214011)

0 引言

运算符和运算对象是表达式的两个组成部分,根据运算符计算对象的数量将其分为单目运算符、双目运算符和三目运算符[1-3].为便于理解,本研究仅讨论由双目运算符构成的表达式.根据运算符和运算对象的相对位置关系可以将表达式分为前缀表达式、中缀表达式和后缀表达式.实际应用中,使用频率最高的是中缀表达式,其运算符的两个运算对象一个置于前面,另一个置于后面.人们习惯使用这种表达式形式,直观上求值也相对容易,但在计算机上对其求值,因为同时要考虑运算符的优先级和结合性,就显得比较困难.对此,本研究提出一种基于二叉树的转换方法.

1 传统的转换方法

通常,将中缀表达式转换为前缀表达式的方法是:把每个运算符的两个运算对象都移到它的后面,然后去除掉所有的括号.因此在前缀表达式中,没有括号运算符,也没有优先级的差别.本研究讨论的运算符及其优先级如表1所示.

表1 各个算术运算符的优先级

表1中,osp称为栈外优先级,isp称为栈内优先级.右括号′)′具有最高的栈外优先级,处理时一遇到′)′立即将其压入栈内,进栈后,其栈内优先级变得很低,仅高于′#′,其目的是便于括号内的其它运算符进栈.其它运算符进栈后优先级数都减1.运算符优先级相等的情况只出现在括号匹配或栈底的′#′号与输入流最后的′#′号匹配时.前者将连续弹出位于栈顶的运算符,直至遇到′)′为止.然后将′)′退栈以成对消除括号,后者将结束算法.

转换后,表达式中运算对象的次序不变,而运算符的次序发生了变化,由处在两个操作对象的中间变为处在两个运算对象的前面,同时去掉了所有的括号.转换过程使用两个栈,一个用来存放运算符,另一个用来保存转换得到的结果.对于存放运算符的栈,先要在栈底放一个特殊运算符,假定为′#′字符,让它具有最低的运算符优先级,假定为数值0.对中缀表达式字符串的扫描是从后向前进行的.

算法具体描述如下:

(1)运算符栈R和保存结果的栈D初始化,将结束符′#′压入栈R,然后读入中缀表达式字符串的最后一个字符ch.

(2)重复执行以下步骤,直到第一个字符:①若ch是运算对象直接压入栈D,读入前一个字符到ch.②若ch是运算符,判断ch的优先级osp和栈R的栈顶运算符op的优先级isp:若osp(ch)>isp(op),将ch压入栈R,读入前一个字符到ch;若osp(ch)< isp(op),将栈R出栈的元素压入到栈D中,继续执行步骤②;若osp(ch)=isp(op),说明ch是字符′(′,对栈R执行退栈操作,读入前一个字符到ch.

(3)将栈R中各个元素依次出栈,再压入到栈D中,直到出栈元素是字符′#′,然后将栈D各个元素依次出栈输出,即得到转换后的前缀表达式.

设以′#′字符作为结束符的中缀表达式已经保存在s1字符串中,转换后得到的前缀表达式存于s2字符串中.由中缀表达式转换为前缀表达式的规则可知:为了使转换正确,需要设定2个栈.

将字符串s1表示的中缀表达式转为前缀表达式算法的基本操作方法是,从后向前扫描中缀表达式中的每个字符,对不同类型的字符分别进行处理.设定一个标识flag,如果扫描到的是非数值字符则将flag置为0;如扫描到的是数值字符则将flag置为1.设定2个栈,一个是存放运算符的栈R,另一个是保存转换结果的栈D.如果扫描到的是空格,则看成分隔符,无需进行处理;若扫描到的是右括号,则将其压入栈R中,等到以它为结束符的括号内的表达式转换完毕后再弹出栈,同时将flag置为0;若扫描到的是左括号,则说明括号内的中缀表达式已经转换结束,将栈R中从栈顶直到对应右括号之间的运算符依次出栈并压入栈D内,同时将flag置为0;若扫描到的是运算符,并且该运算符的优先级不小于栈R的栈顶运算符的优先级时,将它压入栈R内,同时将flag置为0;若扫描到的运算符的优先级小于栈R的栈顶运算符的优先级时,将栈R的栈顶运算符出栈并压入栈D中,直到栈R的栈顶运算符的优先级大于或等于当前运算符的优先级为止,然后将运算符压入栈R内,同时将flag置为0;当中缀表达式字符串扫描结束时将栈R中剩余的所有元素依次出栈并压入栈D内,最后将栈D中元素依次出栈保存在字符串s2中,再向s2末尾加上表达式结束符′#′和字符串结束符′′,这样字符串s2中保存的就是转换得到的前缀表达式.

例如,给定中缀表达式为,(A+B)＊D-E/(F+A＊D)+C,按上述算法执行的转换过程如表2所示.

表2 中缀表达式转换为前缀表达式的过程

然后,对栈D中的元素依次出栈即可得到前缀表达式:+-＊+A B D/E+F＊A D C.

2 基于二叉树的转换方法

2.1 基于二叉树的转换方法

基于二叉树的将中缀表达式转换为前缀表达式的方法的思路是,根据中缀表达式得到与其对应的二叉树,中缀表达式中的运算对象对应二叉树的叶子节点,运算符对应二叉树的分支节点,前序遍历二叉树即可得到中缀表达式对应的前缀表达式.该方法的特点在于可以将中缀表达式转换为后缀表达式和前缀表达式的方法统一起来,方便程序的统一处理.

基于二叉树的转换方法中,运算符以及相应的栈内和栈外优先级见表3.使用2个栈:一个是保存运算符的栈R,另一个保存指向二叉树树根的指针栈PS.

表3 运算符及其优先级

算法具体描述如下:

(1)运算符栈R初始化,将结束符′#′压入栈R.指针栈PS初始化,然后读入中缀表达式字符流的首字符ch.

(2)重复执行以下步骤,直到ch=′#′:①若ch是运算对象,直接将其作为新创建的二叉树的叶子结点,并把指向该叶子结点的指针压入栈PS,读入下一个字符到ch.②若ch是运算符,判断ch的优先级osp和当前运算符栈R栈顶的运算符op的优先级isp:若osp(ch)=isp(op),说明ch是字符′)′,对运算符栈R执行出栈操作,读入下一个字符到ch;若osp(ch)>isp(op),将ch压入运算符栈R,读入下一个字符到ch;若osp(ch)

(3)对指针栈PS的栈顶元素指向的二叉树进行前序遍历,即可得到中缀表达式对应的前缀表达式.

例如,给定中缀表达式为,(A+B)＊D-E/(F+ A＊D)+C,用新方法构建二叉树时具体过程如表4所示,其中,Pi表示指向编号为i结点的指针.