表达式不同形式间转换及二叉树建立研究
2018-09-26肖红德
肖红德
摘要：通过制定表达式转换操作规则，得到了表达式不同表示之间的算法实现过程。通过对表达式不同表示之间转换过程的修改制定，建立对应的二叉树结构操作规则和算法实现过程，最终在表达式和栈结构以及二叉树结构这两个比较重要的数据结构之间建立联系，使表达式相关的操作问题转换为数据结构中栈结构和二叉树结构这两个常用的操作问题，从而将解决问题的操作规则和算法实现过程有机结合起来，使表达式有关问题能通过相应操作规则的制定转换为具体算法实现。
关键词：表达式；二叉树结构；算法实现；操作规则
DOI：10.11907/rjdk.181224
中图分类号：TP3-05
文献标识码：A文章编号：1672-7800（2018）007-0057-07
Abstract：Thepurposeofthisstudyistheapplicationofthestackstructureintheconversionofthedifferentexpressionsoftheexpression.Thisarticleobtainthealgorithmimplementationprocessbetweentheexpressionofdifferentexpressionsbyformulatingtheoperationrulesoftheexpressiontransformation.Finally，thisarticleestablishaconnectionbetweenexpressionsandthetwoimportantdatastructureswhicharestackstructureandtwobinarytreestructure，sothattheexpressionrelatedoperationproblemscanbeconvertedtotwocommonlyusedoperationproblemsinthedatastructurestackstructureandbinarytreestructure.Thenthisarticlecombinetheoperationruleswhichsolvetheproblemsandalgorithmimplementationprocess，whichmaketheproblemsofexpressiontransformthedetailalgorithmimplementationthroughformulatingtherelevantoperationrules.Algorithmimplementationprocessesbetweendifferentexpressionsbyformulatingtheexpressiontransformationrulesareobtained.Theconnectionbetweenstackstructureandbinarytreestructureisestablishedsothattheexpressionsrelatedtooperationproblemscanbeconvertedtothetwocommonoperationproblemsinthestackstructureandbinarytreestructure.Theoperationruleswhichsolvetheproblemsandthealgorithmarecombinedtorealiseoperationruletransformationtospecificalgorithms.
KeyWords：expression；binarytreestructure；algorithmimplementation；operationrules
0引言
表達式是数据对象（可以是常量、变量、表达式）通过运算符（常用的有加（+）、减（-）、乘（*）、除（/）、次方（^）、括号）连接起来组成的式子。表达式的定义与常见数据结构（如二叉树、树、广义表等）的定义类似，是一个递归定义，即数据对象也可以是一个表达式。
一个表达式可以只有一个数据对象，比如变量a、常量100等，也可以是一个表达式a和另一个表达式b通过运算符连接起来的式子，比如a+b。a+b是较常见的表示方法，一般称之为表达式，与表达式对应的有3种表示形式：前缀表达式、中缀表达式和后缀表达式，在这3种表达形式中，只有数据对象和去除改变运算顺序括号之后的运算符，它们之间的区别在于运算符处于数据对象的什么位置。如果运算符处于数据对象前面，称为前缀表达式；如果运算符处于数据对象中间，称为中缀表达式；如果运算符处于数据对象后面，称为后缀表达式。对于表达式a+b，其前缀表达式为+ab，中缀表达式为a+b，后缀表达式为ab+。
由于中缀表达式是去除改变运算顺序括号之后的表达式，因此按照正常运算的结果改变了原有表达式含义，在进行表达式求值时一般使用后缀表达式进行。当然，用前缀表达式对原有表达式进行求值也可按照其固有的运算顺序进行。
表达式不同表示之间的相互转换是数据结构中非常重要的一个内容，它既是栈结构应用的例子，又与二叉树结构联系在一起，是二叉树建立和遍历应用的实例。因此，理解表达式的前缀表达式、后缀表达式的产生，前缀表达式、中缀表达式和后缀表达式之间的转换以及表达式和二叉树结构之间的关系，就能更好地理解数据结构中很重要的栈结构和二叉树结构应用。中缀表达式在原有表达式基础上直接去除括号即可，此过程比较容易实现，本文不作详细介绍。
1表达式研究现状
表达式相关问题主要分为以下几方面：①表达式的应用领域；②由表达式获得前缀表达式；③由表达式获得后缀表达式；④由前缀表达式获得中缀表达式；⑤由前缀表达式获得后缀表达式；⑥由后缀表达式获得前缀表达式；⑦由后缀表达式获得中缀表达式；⑧由表达式、前缀表达式、后缀表达式中的任意一种建立对应的二叉树结构；⑨表达式的求值算法。
前缀表达式、中缀表达式和后缀表达式之间的转换以及表达式的应用方面已有很多研究。文献[1-6]介绍了表达式的具体应用，其中文献[1]介绍了后缀表达式在条形装箱问题中的具体应用，文献[2]介绍了后缀表达式在可扩展的逻辑表达式求值系统中的应用，文献[3]介绍了后缀表达式在遗传编程算法实现中的应用，文献[4]介绍了后缀表达式在岩石地球化学图解辅助分析软件中的应用，文献[5]介绍了后缀表达式在民用飞机机组告警系统试验室自动化测试技术研究中的应用，文献[6]介绍了后缀表达式在可视化公式编辑软件中的应用，文献[7-9]介绍了中缀表达式转换为后缀表达式的算法过程以及表达式和二叉树的对应关系，文献[10]给出了前缀表达式转换为后缀表达式的转换规则，文献[11-13]给出了中缀表达式转换为后缀表达式的具体方法和过程，文献[14]给出了前缀表达式转换为后缀表达式的具体方法和过程，文献[15]给出了中缀表达式转换为前缀表达式的算法过程，文献[16-17]给出了中缀表达式转换为后缀表达式的算法过程以及表达式的求值算法，文献[18]给出了中缀表达式和后缀表达式的求值算法以及后缀表达式转换为前缀表达式的算法过程，文献[19]给出了前缀表达式转换为后缀表达式的算法过程以及后缀表达式的求值算法，文献[20]给出了后缀表达式的求值算法。
二叉树结构对于研究表达式的表示至关重要。对于表达式所对应的二叉树结构，其前序遍历序列对应前缀表达式，中序遍历序列对应中缀表达式，后序遍历序列对应后缀表达式。因此，如果能建立表达式所对应的二叉树结构，则不同表达式之间的转换结果可通过对应的二叉树结构顺利得到。本文主要研究表达式不同形式之间的转换，以及由表达式的不同形式建立对应二叉树结构的操作规则和算法实现。
2表达式不同形式之间的相互转换
2.1算法准备
对于表达式的不同表示，需要考虑运算符出现的次序问题，对不同的运算符进行优先级排序，本文以加（+）、减（-）、乘（*）、除（/）、次方（^）为例进行说明。
定义以下优先关系，如表1所示。
在得到不同运算符之间的优先关系后，就可以定义与运算符对应的优先级：加（+）和减（-）的优先级为1；乘（*）和除（/）的优先级为2；次方（^）的优先级为3。优先级越大，表示在進行运算时越需要优先执行。在后面的算法设计部分，为便于比较和判断运算符是否处理完成，定义符号“#”的优先级为-1，“（”的优先级为0。
由于括号运算符是用于改变运算顺序的，先算括号内后算括号外，与一般的运算符差别较大，因此，要在需要处理括号的各个算法中单独处理。
为方便处理，限定表达式的表示，使用变量名长度为1的字符表示数据对象，数据对象和运算符之间没有空格，后面的算法只考虑小括号情况。
后续算法实现过程中用到的函数说明如下：
initstack（stack）：初始化栈stack；
push（stack，obj）：将变量obj压入栈stack；
pop（stack，ch）：从栈stack出栈一个元素并把该元素放到变量ch中，如果没有带参数ch，表示从栈stack出栈一个元素作为函数返回值；
strcat（obj1，obj2，obj3）：将3个变量obj1、obj2、obj3顺序连接成一个字符串；
percede（ch）：获得运算符ch的优先级；
gettop（stack）：从栈stack中获得栈顶元素；
stacklength（stack）：返回栈stack中的元素个数；
dataobject（ch）：判断变量ch是否为数据对象，如果是，则返回true，否则返回false；
stack_trans_prefix（stack1，stack2）：表示将一个表达式转换为对应的前缀表达式过程，从栈stack1中出栈一个元素，从栈stack2中出栈两个元素，将出栈的3个元素连接成的一个前缀表达式变量，压入栈stack2，具体运算过程如下：
op=pop（stack1）；//从栈stack1中出栈一个元素赋值给变量op
c2=pop（stack2）；//从栈stack2中出栈一个元素赋值给变量c2
c1=pop（stack2）；//从栈stack2中出栈一个元素赋值给变量c1
str=strcat（op，c1，c2）；//将c1、c2、op顺序连接为一个字符串并赋值给变量str
push（stack2，str）；//将变量str压入栈stack2
stack_trans_in（stack1，stack2）表示将一个表达式转换为对应的中缀表达式过程，从栈stack1中出栈一个元素，从栈stack2中出栈两个元素，并将出栈的3个元素连接成的一个中缀表达式变量压入栈stack2，具体运算过程如下：
op=pop（stack1）；//从栈stack1中出栈一个元素赋值给变量op
c2=pop（stack2）；//从栈stack2中出栈一个元素赋值给变量c2
c1=pop（stack2）；//从栈stack2中出栈一个元素赋值给变量c1
str=strcat（c1，op，c2）；//将c1、c2、op顺序连接为一个字符串并赋值给变量str
push（stack2，str）；//将变量str压入栈stack2
stack_trans_post（stack1，stack2）表示将一个表达式转换为对应的后缀表达式的过程，从栈stack1中出栈一个元素，从栈stack2中出栈两个元素，并将出栈的3个元素连接成的一个后缀表达式变量压入栈stack2，具体运算过程如下：
op=pop（stack1）；//从栈stack1中出栈一个元素赋值给变量op
c2=pop（stack2）；//从栈stack2中出栈一個元素赋值给变量c2
c1=pop（stack2）；//从栈stack2中出栈一个元素赋值给变量c1
str=strcat（c1，c2，op）；//将c1、c2、op顺序连接为一个字符串并赋值给变量str
push（stack2，str）；//将变量str压入栈stack2
注：后面的算法实现只给出主要部分，一些变量的初始化部分略去。
2.2由表达式获得对应的前缀表达式
2.2.1操作规则
由表达式获得对应前缀表达式的主要操作规则：将表达式的运算符向前移动到参与运算的两个数据对象之前，这里的运算符是普通的算术运算符，不包括括号，对于括号需要成对进行处理；数据对象可以是一个变量名，也可以是一个前缀表达式。在设计更为详细的操作规则时，需要对运算符的优先级进行判断处理。
2.2.2算法实现
由表达式获得对应前缀表达式的算法实现需要借助两个辅助栈stack_data和stack_symbol进行。其中，stack_data栈中存放变量名或前缀表达式，stack_symbol栈用来存放运算符，函数名为TransFromExptoPrefix，参数prefix表示最终得到的前缀表达式存放到数组的名称。参数exp表示最初的表达式，其主要思想是每次遇到运算符时，需要将该运算符与栈stack_symbol中的运算符进行比较。如果该运算符的优先级比栈stack_symbol栈顶的运算符优先级高，则将该运算符压入栈stack_symbol，否则从栈stack_symbol中出栈一个运算符，从栈stack_data中出栈两个数据对象，连接成一个前缀表达式压入栈stack_data。将当前运算符压入栈stack_symbol；每次遇到数据对象（即变量名）时将该变量压入栈stack_data。函数表示过程如下：
voidTransFromExptoPrefix（charprefix[]，charexp[]）{
push（stack_symbol，'#'）；
while（（ch=exp[i++]）！='＼＼0'）{
if（dataobject（ch））push（stack_data，ch）；
else{
switch（ch）{
case'（'：push（stack_symbol，ch）；break；
case'）'：while（gettop（stack_symbol）！='（'）{
stack_trans_prefix（stack_symbol，stack_data）；}
pop（stack_symbol）；break；
default：while（percede（ch）<=percede（gettop（stack_symbol）））{
stack_trans_prefix（stack_symbol，stack_data）；}
push（stack_symbol，ch）；break；}
}
}
while（（ch=gettop（stack_symbol））！='#'）{
stack_trans_prefix（stack_symbol，stack_data）；}
pop（stack_data，prefix）；
}
2.3由表达式获得对应的后缀表达式
2.3.1操作规则
由表达式获得对应后缀表达式的主要操作规则：将表达式的运算符向后移动到参与运算的两个数据对象之后，这里的运算符是普通算术运算符，不包括括号，对于括号的处理需要成对进行；数据对象可以是一个变量名，也可以是一个后缀表达式。在设计更为详细的操作规则时，需要对运算符的优先级进行处理。
2.3.2算法实现
由表达式获得对应后缀表达式的算法实现需要借助两个辅助栈stack_data和stack_symbol进行。其中，stack_data栈中存放变量名或后缀表达式，stack_symbol栈用来存放运算符，函数名为TransFromExptoPost，参数post表示最终得到的后缀表达式存放的数组名称，参数exp表示最初的表达式。其主要思想是每次遇到运算符时，需要将该运算符与栈stack_symbol中栈顶的运算符进行比较。如果该运算符的优先级比栈stack_symbol栈顶的运算符优先级高，则将该运算符压入栈stack_symbol；否则，当栈stack_symbol中栈顶元素运算符优先级大于等于当前遇到的运算符时，需要进行以下处理：从栈stack_data中出栈两个数据对象，从栈stack_symbol中出栈一个运算符，连接成一个后缀表达式压入栈stack_data，然后将当前运算符压入栈stack_symbol；每次遇到数据对象（即变量名），则将该数据对象压入栈stack_data。其函数表示过程如下：
voidTransFromExptoPost（charpost[]，charexp[]）{
push（stack_symbol，'#'）；
while（（ch=exp[i++]）！='＼＼0'）{
if（dataobject（ch））push（stack_data，ch）；
else{
switch（ch）{
case'（'：push（stack_symbol，ch）；break；
case'）'：while（getpop（stack_symbol）！='（'）{
stack_trans_post（stack_symbol，stack_data）；}
pop（stack_symbol）；break；
default：while（percede（ch）<=percede（gettop（stack_symbol）））{
stack_trans_post（stack_symbol，stack_data）；}
push（stack_symbol，ch）；break；}
}
}
while（（ch=gettop（stack_symbol））！='#'）{
stack_trans_post（stack_symbol，stack_data）；}
pop（stack_data，post）；
}
2.4由前綴表达式获得对应的中缀表达式
2.4.1操作规则
由前缀表达式获得对应中缀表达式的操作规则：将前缀表达式的运算符向后移动到参与运算的两个数据对象之间。这里所说的运算符是普通的算术运算符，没有括号；数据对象可以是一个变量名，也可以是一个中缀表达式。由前缀表达式获得对应的中缀表达式不需要考虑运算符的优先级，只需要考虑运算符出现的先后以及数据对象出现的位置。
2.4.2算法实现
由前缀表达式获得对应中缀表达式的算法实现需要借助两个辅助栈stack_data和stack_symbol进行。其中，stack_data栈中存放变量名或中缀表达式，stack_symbol栈用来存放运算符，函数名为TransFromPrefixtoIn，参数in表示最终得到的中缀表达式存放的数组名称，参数prefix表示最初的前缀表达式。其主要思想是每次遇到运算符时，将运算符压入栈stack_symbol。每次遇到数据对象时判断是否是连续的两个对象，如果是，则将连续的两个数据对象从栈stack_data中出栈，与栈stack_symbol出栈的运算符结合为中缀表达式，然后压入栈stack_data。为了判断是否遇到了连续的两个数据对象，需要在压入第一个数据元素至栈stack_data时，压入栈stack_symbol的一个特殊元素（'&'），表示数据对象中已经出现了一个元素。其函数表示过程如下：
voidTransFromPrefixtoIn（charin[]，charprefix[]）{
while（（ch=prefix[i++]）！='＼＼0'）{
if（dataobject（ch））{
push（stack_data，ch）；
while（gettop（stack_symbol）=='&'）{
stack_trans_in（stack_symbol，stack_data）；}
push（stack_symbol，'&'）；}
elsepush（stack_symbol，ch）；
}
pop（stack_data，in）；
}
2.5由前缀表达式获得对应的后缀表达式
2.5.1操作规则
由前缀表达式获得对应后缀表达式的操作规则：将前缀表达式的运算符向后移动到参与运算的两个数据对象之后。这里所说的运算符是普通的算术运算符，没有括号；数据对象可以是一个变量名，也可以是一个后缀表达式。由前缀表达式获得对应的后缀表达式不需要考虑运算符的优先级，只需考虑运算符出现的先后以及数据对象出现的位置。
2.5.2算法实现
由前缀表达式获得对应后缀表达式的算法实现需要借助两个辅助栈stack_data和stack_symbol进行。其中，stack_data栈中存放变量名或后缀表达式，stack_symbol栈用来存放运算符，函数名为TransFromPrefixtoPost，参数post表示最终得到的后缀表达式存放的数组名称，参数prefix表示最初的前缀表达式。其主要思想是每次遇到运算符时，将运算符压入栈stack_symbol。每次遇到数据对象，将数据对象压入栈stack_data，然后判断是否是连续的两个数据对象。如果是，则将连续的两个数据对象从栈stack_data出栈与stack_symbol栈顶出栈运算结合为后缀表达式，然后压入栈stack_data，最后向栈stack_symbol压入元素'&'。为了判断是否遇到了连续的两个数据对象，需要在压入第一个数据元素至栈stack_data时，压入栈stack_symbol一个特殊元素（'&'），表示数据对象中已经出现了一个元素。其函数表示过程如下：
voidTransFromPrefixtoPost（charpost[]，charprefix[]）{
while（（ch=prefix[i++]）！='＼＼0'）{
if（dataobject（ch））{
push（stack_data，ch）；
if（gettop（stack_symbol）！='&'）push（stack_symbol，'&'）；
else{
while（gettop（stack_symbol）=='&'）{
pop（stack_symbol）；
stack_trans_post（stack_symbol，stack_data）；}
push（stack_symbol，'&'）；}
}
elsepush（stack_symbol，ch）；
}
pop（stack_data，post）；
}
2.6由后綴表达式获得对应的前缀表达式
2.6.1操作规则
由后缀表达式获得对应前缀表达式的主要操作规则：将后缀表达式的运算符向前移动到参与运算的两个数据对象之前。这里所说的运算符是普通的算术运算符，没有括号；数据对象可以是一个变量名，也可以是一个前缀表达式。由后缀表达式获得对应的前缀表达式不需要考虑运算符的优先级，只需考虑运算符出现的先后以及数据对象出现的位置。
2.6.2算法实现
由后缀表达式获得对应前缀表达式的算法实现需要借助一个辅助栈stack_data进行。stack_data栈中用于存放变量名或前缀表达式，函数名为TransFromPosttoPrefix，参数prefix表示最终的前缀表达式存放的数组名称，参数post表示最初的后缀表达式。其主要思想是每次遇到数据对象（即变量名）时，将该数据对象压入栈stack_data，每次遇到运算符，从栈stack_data出栈两个数据对象并和该运算符连接成前缀表达式，然后将该前缀表达式压入栈stack_data。其函数表示过程如下：
voidTransFromPosttoPrefix（charprefix[]，charpost[]）{
while（（ch=post[i++]）！='＼＼0'）{
if（dataobject（ch））push（stack_data，ch）；
else{
obj2=pop（stack_data）；obj1=pop（stack_data）；
push（stack_data，strcat（ch，obj1，obj2））；}
}
pop（stack_data，prefix）；
}
2.7由后缀表达式获得对应的中缀表达式
2.7.1操作规则
由后缀表达式获得对应中缀表达式的主要操作规则：将后缀表达式的运算符向前移动到参与运算的两个数据对象之间。这里所说的运算符是普通的算术运算符，没有括号；数据对象可以是一个变量名，也可以是一个中缀表达式。由后缀表达式获得对应的中缀表达式不需要考虑运算符的优先级，只需考虑运算符出现的先后以及数据对象出现的位置。
2.7.2算法实现
由后缀表达式获得对应中缀表达式的算法实现需要借助一个辅助栈stack_data进行。stack_data栈中用于存放变量名或中缀表达式，函数名为TransFromPosttoIn，参数in表示最终得到的中缀表达式存放的数组名称，参数post表示最初的后缀表达式。其主要思想是每次遇到数据对象（即变量名）时，将数据对象压入栈stack_data，每次遇到运算符，则从栈stack_data出栈两个数据对象并和该运算符连接成中缀表达式，然后将该中缀表达式压入栈stack_data。其函数表示过程如下：
voidTransFromPosttoIn（charin[]，charpost[]）{
while（（ch=post[i++]）！='＼＼0'）{
if（dataobject（ch））push（stack_data，ch）；
else{
obj2=pop（stack_data）；obj1=pop（stack_data）；
push（stack_data，strcat（obj1，ch，obj2））；}
}
pop（stack_data，in）；
}
2.8案例分析
示例：对于表达式"（a+b）*（c-d）-（e+f）"，通过上面的算法实现过程可以得到其前缀表达式为：-*+ab-cd+ef，后缀表达式为：ab+cd-*ef+-，前缀表达式、中缀表达式和后缀表达式之间的相互转换也可按照上面的算法实现过程分别得到，这里不再详述。
3对应二叉树结构建立
3.1算法准备
为了后面算法表示方便，先对以下函数的含义进行说明：
t=CreateNewNode（ch）：表示新建一个数据域为ch且左、右孩子均为空的二叉树结点，并将该结点的指针赋值给变量t；
stack_trans_tree（stack_symbol，stack_tree）：表示从stack_symbol出栈一个元素并以该元素为数据域建立一个二叉树结点。从stack_tree出栈两个元素，将新建立的二叉树结点的左右两个孩子分别指向这两个元素，然后将该二叉树结点指针压入栈stack_tree，具体执行过程如下：
ch=pop（stack_symbol）；t=CreateNewNode（ch）；
r=pop（stack_tree）；l=pop（stack_tree）；
t->lchile=l；t->rchild=r；
push（stack_tree，t）；
3.2由表达式建立对应的二叉树结构
3.2.1操作规则
由表达式建立对应二叉树结构主要有两种思路：①按照由表达式获得对应的前缀表达式进行；②按照由表达式获得对应的后缀表达式进行。这里以由表达式获得对应的后缀表达式思路设计操作规则：遇到运算符，则按照运算符优先级判断是否需要处理之前的运算符，如果当前运算符的优先级不大于之前的运算符优先级，则需要处理之前的运算符。处理过程为：将之前的运算符作为创建二叉树结点的数据域，并将其左右指针指向最近处理好的二叉树结构，然后将该二叉树结点指针作为最新出现的二叉树结构；如果遇到数据对象（即变量名），则以该数据对象作为数据域建立一个二叉树结点并且其左右孩子均为空，以该二叉树结点指针作为最新出现的二叉树结构。这里所说的运算符包括对括号的处理，括号处理需要成对进行；数据对象是一个以二叉树结点指针为代表的二叉树结构。
3.2.2算法实现
由表达式建立对应二叉树结构的算法实现可按照由表达式获得对应的前缀表达式思路进行，也可按照由表达式获得对应的后缀表达式思路進行，本文按由表达式获得对应的后缀表达式思路进行。与由表达式获得对应的后缀表达式过程类似，需要借助两个辅助栈stack_tree和stack_symbol进行。其中，stack_tree栈中存放建立的二叉树结点指针，stack_symbol栈用来存放运算符，函数名为CreateBiTreeFromExp，参数T表示最终得到的二叉树结构的根结点指针，参数exp表示最初的表达式。其函数表示过程如下：
voidCreateBiTreeFromExp（BiTree&T;，charexp[]）{
push（stack_symbol，'#'）；
while（（ch=exp[i++]）！='＼＼0'）{
if（dataobject（ch））push（stack_tree，CreateNewNode（ch））；
else{
switch（ch）{
case'（'：push（stack_symbol，ch）；break；
case'）'：while（getpop（stack_symbol）！='（'）{
stack_trans_tree（stack_symbol，stack_tree）；}
pop（stack_symbol）；break；
default：
while（percede（ch）<=percede（gettop（stack_symbol）））{
stack_trans_tree（stack_symbol，stack_tree）；}
push（stack_symbol，ch）；break；}
}
}
while（（ch=gettop（stack_symbol））！='#'）{
stack_trans_tree（stack_symbol，stack_tree）；}
pop（stack_tree，T）；
}
3.3由前缀表达式建立对应的二叉树结构
3.3.1操作规则
由前缀表达式建立对应二叉树结构主要操作规则：遇到数据对象（即变量名），则以该数据对象为数据域新建一个二叉树结点结构并其左右孩子均为空，然后判断是否已经连续两次出现了数据对象。如果是，则将之前出现的运算符为数据域创建二叉树结点，并将其左右指针指向最近得到的两个二叉树结构，然后将该二叉树结点指针作为最新出现的二叉树结构；如果遇到运算符则暂时不予处理。由前缀表达式建立对应的二叉树结构，不需要考虑运算符的优先级，只需考虑运算符出现先后以及数据对象出现的位置。
3.3.2算法实现
由前缀表达式建立对应二叉树结构的算法实现需要借助两个辅助栈stack_tree和stack_symbol进行。其中，stack_tree栈中存放二叉树结点指针，stack_symbol栈用来存放运算符，函数名为CreateBiTreeFromPrefix，参数T表示最终得到的二叉树结构的根结点指针，参数prefix表示最初的前缀表达式。其主要思想是每次遇到运算符时，将运算符压入栈stack_symbol，每次遇到数据对象（即变量名）则以该数据对象为数据域创建一个二叉树结点，且其左、右孩子均为空并压入栈stack_tree，然后判断是否是出现了连续的两个数据对象。如果是，则将连续的两个数据对象建立的二叉树结点作为以stack_symbol栈顶出栈运算符作为数据域的二叉树结点的左右孩子，然后将新建立的二叉树结点指针压入栈stack_tree。为了判断是否出现了连续的两个数据对象，需要在压入第一个数据元素至栈stack_tree时，压入栈stack_symbol一个特殊元素'&'，表示数据对象中已经出现了一个元素。如果栈stack_symbol栈顶元素已经是'&'则不进行压入。其函数表示过程如下：
voidCreateBiTreeFromSuffix（BiTree&T;，charsuffix[]）{
while（（ch=prefix[i++]）！='＼＼0'）{
if（dataobject（ch））{
push（stack_tree，CreateNewNode（ch））；
if（gettop（stack_symbol）！='&'）push（stack_symbol，'&'）；
else{
while（gettop（stack_symbol）=='&'）{
pop（stack_symbol）；
stack_trans_tree（stack_symbol，stack_tree）；}
push（stack_symbol，'&'）；}
}
elsepush（stack_symbol，ch）；
}
pop（stack_tree，T）；
}
3.4由后缀表达式建立对应的二叉树结构
3.4.1操作规则
由后缀表达式获得对应二叉树结构的操作规则：遇到数据对象（即变量名），则以该数据对象为数据域新建一个二叉树结点并且其左右孩子均为空，以该二叉树结点指针作为最新出现的二叉树结构；如果遇到运算符，则以该运算符作为数据域新建一个二叉树结点结构，并将其左右孩子分别指向最近出现的两个二叉树结构，然后将该二叉树结点指针作为最近出现的二叉树结构。由后缀表达式获得对应的二叉树结构，不需要考虑运算符的优先级，只需要考虑运算符出现的先后以及数据对象出现的位置。
3.4.2算法实现
由后缀表达式建立对应二叉树结构的算法实现需要借助一个辅助栈stack_tree进行。stack_tree栈中用于存放二叉树结点指针为代表的二叉树结构，函数名为CreateBiTreeFromPost，参数T表示最终得到的二叉树结构的根结点指针，参数post表示最初的后缀表达式。其主要思想是每次遇到数据对象（即变量名），则以该数据对象为数据域创建一个二叉树结点且其左、右孩子均为空，然后将其压入栈stack_tree，每次遇到运算符，则从栈stack_tree出栈两个元素，然后以该运算符为数据域新建一个二叉树结点，并且其左右孩子指针指向出栈的两个元素，然后将新建的二叉树结点指针压入栈stack_tree。其函数表示过程如下：
voidCreateBiTreeFromPost（BiTree&T;，charpost[]）{
while（（ch=post[i++]）！='＼＼0'）{
if（dataobject（ch））push（stack_tree，CreateNewNode（ch））；
else{
t=CreateNewNode（ch）；r=pop（stack_tree）；l=pop（stack_tree）；
t->lchild=l；t->rchild=r；push（stack_tree，t）；
}
}
pop（stack_tree，T）；
}
3.5案例分析
例：对于表达式"（a+b）*（c-d）-（e+f）"，通过上面的算法实现过程可以建立对应的二叉树结构，如图1所示。其详细建立过程这里不再详述。在建立二叉树结构的基础上，其前序遍历、中序遍历、后序遍历分别对应前缀表达式、中缀表达式和后缀表达式。
4结语
对于栈的应用，比较重要的一点就是在设计算法之前，需要弄清楚遇到不同情况时的操作规则，在弄清楚操作规则之后再设计好栈中需要存放元素的数据类型，然后按照操作规则确定相应进栈和出栈情况，以及进栈和出栈之前及之后需要处理内容。栈的应用是数据结构中非常重要的内容，在遇到实际问题时需要先对问题进行分析，判断其需要哪种数据结构解决，然后再按照该数据结构特点进行分析和处理。
参考文献：
[1]汤岩，贾红雨，纪贤标.条形装箱问题的基于后缀表达式的混合遗传算法[J].喀什师范学院学报，2007，28（3）：76-78.
[2]熊风光，况立群，韩焱.可扩展的逻辑表达式求值系统的设计与实现[J].计算机工程与设计，2012，33（10）：3858-3861.
[3]李良敏.遗传编程的MATLAB语言实现[J].计算机工程，2005，31（13）：87-89.
[4]薛涛，刁明光，吕志成.岩石地球化学图解辅助分析软件的关键问题及解决方法[J].现代地质，2013，27（6）：1316-1322.
[5]王焕宇.民用飞机机组告警系统试验室自动化测试技术研究[J].科技创新导报，2016，13（6）：7-10.
[6]张超超.可视化公式编辑软件的设计与实现[J].科学与财富，2015（9）：94-97.
[7]郭群.逆波兰式探微——后缀表达式的求法及其适用情况比较[J].黑龙江科技信息，2007（16）：36-36.
[8]李艳玲.数据结构中实现表达式求值算法的巧妙转换[J].职大学报，2005（4）：62-63.
[9]郭萌萌，许永昌.中綴及后缀算术表达式在运算中的应用研究[J].电脑知识与技术，2009，5（32）：8921-8923.
[10]周欣.逆波兰式转换规则的推导过程[J].电脑编程技巧与维护，2016（21）：35-36.
[11]颜晶晶，张涛.将中缀表达式转换成后缀表达式的三种方法[J].计算机与网络，2004（16）：54-55.
[12]胡云，毛万年.一种将中缀表达式转换为后缀表达式的新方法[J].成都大学学报：自然科学版，2008，27（1）：52-55.
[13]朱玉娟.论中缀表达式与后缀表达式的转换[J].现代商贸工业，2008，20（6）：258-259.
[14]沈华.一种前缀表达式直接转换为后缀表达式的算法[J].电脑编程技巧与维护，2013（2）：12-14.
[15]曹晓丽，潘颖.一种利用栈实现中缀表达式向前缀表达式转换方法的改进[J].甘肃科技，2006，22（11）：64-66.
[16]李世华，刘晓娟，姜晨，等.关于表达式求值的算法研究与实现[J].甘肃科技，2011，27（1）：11-15.
[17]肖巍.基于C#的表达式解析器设计方法[J].长春教育学院学报，2010，26（6）：125-126.
[18]李橙，丁国栋.栈在表达式求值中的应用[J].电脑知识与技术，2014（34）：8156-8157.
[19]钱学林.算术表达式计算的实现[J].电子世界，2014（4）：167-170.
[20]王若民.后缀表达式及其多位数的算术运算探析[J].科教文汇，2007（30）：215-216.
（责任编辑：杜能钢）
