表達式不同形式間轉換及二叉樹建立研究

肖紅德

摘要：通過制定表達式轉換操作規則，得到了表達式不同表示之間的算法實現過程。通過對表達式不同表示之間轉換過程的修改制定，建立對應的二叉樹結構操作規則和算法實現過程，最終在表達式和棧結構以及二叉樹結構這兩個比較重要的數據結構之間建立聯系，使表達式相關的操作問題轉換為數據結構中棧結構和二叉樹結構這兩個常用的操作問題，從而將解決問題的操作規則和算法實現過程有機結合起來，使表達式有關問題能通過相應操作規則的制定轉換為具體算法實現。

關鍵詞：表達式；二叉樹結構；算法實現；操作規則

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.

（責任編輯：杜能鋼）