表達(dá)式不同形式間轉(zhuǎn)換及二叉樹建立研究

肖紅德

摘要：通過制定表達(dá)式轉(zhuǎn)換操作規(guī)則，得到了表達(dá)式不同表示之間的算法實(shí)現(xiàn)過程。通過對表達(dá)式不同表示之間轉(zhuǎn)換過程的修改制定，建立對應(yīng)的二叉樹結(jié)構(gòu)操作規(guī)則和算法實(shí)現(xiàn)過程，最終在表達(dá)式和棧結(jié)構(gòu)以及二叉樹結(jié)構(gòu)這兩個比較重要的數(shù)據(jù)結(jié)構(gòu)之間建立聯(lián)系，使表達(dá)式相關(guān)的操作問題轉(zhuǎn)換為數(shù)據(jù)結(jié)構(gòu)中棧結(jié)構(gòu)和二叉樹結(jié)構(gòu)這兩個常用的操作問題，從而將解決問題的操作規(guī)則和算法實(shí)現(xiàn)過程有機(jī)結(jié)合起來，使表達(dá)式有關(guān)問題能通過相應(yīng)操作規(guī)則的制定轉(zhuǎn)換為具體算法實(shí)現(xiàn)。

關(guān)鍵詞：表達(dá)式；二叉樹結(jié)構(gòu)；算法實(shí)現(xiàn)；操作規(guī)則

DOI：10.11907/rjdk.181224

中圖分類號：TP3-05

文獻(xiàn)標(biāo)識碼：A文章編號：1672-7800（2018）007-0057-07

Abstract：Thepurposeofthisstudyistheapplicationofthestackstructureintheconversionofthedifferentexpressionsoftheexpression.Thisarticleobtainthealgorithmimplementationprocessbetweentheexpressionofdifferentexpressionsbyformulatingtheoperationrulesoftheexpressiontransformation.Finally，thisarticleestablishaconnectionbetweenexpressionsandthetwoimportantdatastructureswhicharestackstructureandtwobinarytreestructure，sothattheexpressionrelatedoperationproblemscanbeconvertedtotwocommonlyusedoperationproblemsinthedatastructurestackstructureandbinarytreestructure.Thenthisarticlecombinetheoperationruleswhichsolvetheproblemsandalgorithmimplementationprocess，whichmaketheproblemsofexpressiontransformthedetailalgorithmimplementationthroughformulatingtherelevantoperationrules.Algorithmimplementationprocessesbetweendifferentexpressionsbyformulatingtheexpressiontransformationrulesareobtained.Theconnectionbetweenstackstructureandbinarytreestructureisestablishedsothattheexpressionsrelatedtooperationproblemscanbeconvertedtothetwocommonoperationproblemsinthestackstructureandbinarytreestructure.Theoperationruleswhichsolvetheproblemsandthealgorithmarecombinedtorealiseoperationruletransformationtospecificalgorithms.

KeyWords：expression；binarytreestructure；algorithmimplementation；operationrules

0引言

表達(dá)式是數(shù)據(jù)對象（可以是常量、變量、表達(dá)式）通過運(yùn)算符（常用的有加（+）、減（-）、乘（*）、除（/）、次方（^）、括號）連接起來組成的式子。表達(dá)式的定義與常見數(shù)據(jù)結(jié)構(gòu)（如二叉樹、樹、廣義表等）的定義類似，是一個遞歸定義，即數(shù)據(jù)對象也可以是一個表達(dá)式。

一個表達(dá)式可以只有一個數(shù)據(jù)對象，比如變量a、常量100等，也可以是一個表達(dá)式a和另一個表達(dá)式b通過運(yùn)算符連接起來的式子，比如a+b。a+b是較常見的表示方法，一般稱之為表達(dá)式，與表達(dá)式對應(yīng)的有3種表示形式：前綴表達(dá)式、中綴表達(dá)式和后綴表達(dá)式，在這3種表達(dá)形式中，只有數(shù)據(jù)對象和去除改變運(yùn)算順序括號之后的運(yùn)算符，它們之間的區(qū)別在于運(yùn)算符處于數(shù)據(jù)對象的什么位置。如果運(yùn)算符處于數(shù)據(jù)對象前面，稱為前綴表達(dá)式；如果運(yùn)算符處于數(shù)據(jù)對象中間，稱為中綴表達(dá)式；如果運(yùn)算符處于數(shù)據(jù)對象后面，稱為后綴表達(dá)式。對于表達(dá)式a+b，其前綴表達(dá)式為+ab，中綴表達(dá)式為a+b，后綴表達(dá)式為ab+。

由于中綴表達(dá)式是去除改變運(yùn)算順序括號之后的表達(dá)式，因此按照正常運(yùn)算的結(jié)果改變了原有表達(dá)式含義，在進(jìn)行表達(dá)式求值時一般使用后綴表達(dá)式進(jìn)行。當(dāng)然，用前綴表達(dá)式對原有表達(dá)式進(jìn)行求值也可按照其固有的運(yùn)算順序進(jìn)行。

表達(dá)式不同表示之間的相互轉(zhuǎn)換是數(shù)據(jù)結(jié)構(gòu)中非常重要的一個內(nèi)容，它既是棧結(jié)構(gòu)應(yīng)用的例子，又與二叉樹結(jié)構(gòu)聯(lián)系在一起，是二叉樹建立和遍歷應(yīng)用的實(shí)例。因此，理解表達(dá)式的前綴表達(dá)式、后綴表達(dá)式的產(chǎn)生，前綴表達(dá)式、中綴表達(dá)式和后綴表達(dá)式之間的轉(zhuǎn)換以及表達(dá)式和二叉樹結(jié)構(gòu)之間的關(guān)系，就能更好地理解數(shù)據(jù)結(jié)構(gòu)中很重要的棧結(jié)構(gòu)和二叉樹結(jié)構(gòu)應(yīng)用。中綴表達(dá)式在原有表達(dá)式基礎(chǔ)上直接去除括號即可，此過程比較容易實(shí)現(xiàn)，本文不作詳細(xì)介紹。

1表達(dá)式研究現(xiàn)狀

表達(dá)式相關(guān)問題主要分為以下幾方面：①表達(dá)式的應(yīng)用領(lǐng)域；②由表達(dá)式獲得前綴表達(dá)式；③由表達(dá)式獲得后綴表達(dá)式；④由前綴表達(dá)式獲得中綴表達(dá)式；⑤由前綴表達(dá)式獲得后綴表達(dá)式；⑥由后綴表達(dá)式獲得前綴表達(dá)式；⑦由后綴表達(dá)式獲得中綴表達(dá)式；⑧由表達(dá)式、前綴表達(dá)式、后綴表達(dá)式中的任意一種建立對應(yīng)的二叉樹結(jié)構(gòu)；⑨表達(dá)式的求值算法。

前綴表達(dá)式、中綴表達(dá)式和后綴表達(dá)式之間的轉(zhuǎn)換以及表達(dá)式的應(yīng)用方面已有很多研究。文獻(xiàn)[1-6]介紹了表達(dá)式的具體應(yīng)用，其中文獻(xiàn)[1]介紹了后綴表達(dá)式在條形裝箱問題中的具體應(yīng)用，文獻(xiàn)[2]介紹了后綴表達(dá)式在可擴(kuò)展的邏輯表達(dá)式求值系統(tǒng)中的應(yīng)用，文獻(xiàn)[3]介紹了后綴表達(dá)式在遺傳編程算法實(shí)現(xiàn)中的應(yīng)用，文獻(xiàn)[4]介紹了后綴表達(dá)式在巖石地球化學(xué)圖解輔助分析軟件中的應(yīng)用，文獻(xiàn)[5]介紹了后綴表達(dá)式在民用飛機(jī)機(jī)組告警系統(tǒng)試驗(yàn)室自動化測試技術(shù)研究中的應(yīng)用，文獻(xiàn)[6]介紹了后綴表達(dá)式在可視化公式編輯軟件中的應(yīng)用，文獻(xiàn)[7-9]介紹了中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法過程以及表達(dá)式和二叉樹的對應(yīng)關(guān)系，文獻(xiàn)[10]給出了前綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的轉(zhuǎn)換規(guī)則，文獻(xiàn)[11-13]給出了中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的具體方法和過程，文獻(xiàn)[14]給出了前綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的具體方法和過程，文獻(xiàn)[15]給出了中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式的算法過程，文獻(xiàn)[16-17]給出了中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法過程以及表達(dá)式的求值算法，文獻(xiàn)[18]給出了中綴表達(dá)式和后綴表達(dá)式的求值算法以及后綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式的算法過程，文獻(xiàn)[19]給出了前綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法過程以及后綴表達(dá)式的求值算法，文獻(xiàn)[20]給出了后綴表達(dá)式的求值算法。

二叉樹結(jié)構(gòu)對于研究表達(dá)式的表示至關(guān)重要。對于表達(dá)式所對應(yīng)的二叉樹結(jié)構(gòu)，其前序遍歷序列對應(yīng)前綴表達(dá)式，中序遍歷序列對應(yīng)中綴表達(dá)式，后序遍歷序列對應(yīng)后綴表達(dá)式。因此，如果能建立表達(dá)式所對應(yīng)的二叉樹結(jié)構(gòu)，則不同表達(dá)式之間的轉(zhuǎn)換結(jié)果可通過對應(yīng)的二叉樹結(jié)構(gòu)順利得到。本文主要研究表達(dá)式不同形式之間的轉(zhuǎn)換，以及由表達(dá)式的不同形式建立對應(yīng)二叉樹結(jié)構(gòu)的操作規(guī)則和算法實(shí)現(xiàn)。

2表達(dá)式不同形式之間的相互轉(zhuǎn)換

2.1算法準(zhǔn)備

對于表達(dá)式的不同表示，需要考慮運(yùn)算符出現(xiàn)的次序問題，對不同的運(yùn)算符進(jìn)行優(yōu)先級排序，本文以加（+）、減（-）、乘（*）、除（/）、次方（^）為例進(jìn)行說明。

定義以下優(yōu)先關(guān)系，如表1所示。

在得到不同運(yùn)算符之間的優(yōu)先關(guān)系后，就可以定義與運(yùn)算符對應(yīng)的優(yōu)先級：加（+）和減（-）的優(yōu)先級為1；乘（*）和除（/）的優(yōu)先級為2；次方（^）的優(yōu)先級為3。優(yōu)先級越大，表示在進(jìn)行運(yùn)算時越需要優(yōu)先執(zhí)行。在后面的算法設(shè)計部分，為便于比較和判斷運(yùn)算符是否處理完成，定義符號“#”的優(yōu)先級為-1，“（”的優(yōu)先級為0。

由于括號運(yùn)算符是用于改變運(yùn)算順序的，先算括號內(nèi)后算括號外，與一般的運(yùn)算符差別較大，因此，要在需要處理括號的各個算法中單獨(dú)處理。

為方便處理，限定表達(dá)式的表示，使用變量名長度為1的字符表示數(shù)據(jù)對象，數(shù)據(jù)對象和運(yùn)算符之間沒有空格，后面的算法只考慮小括號情況。

后續(xù)算法實(shí)現(xiàn)過程中用到的函數(shù)說明如下：

initstack（stack）：初始化棧stack；

push（stack，obj）：將變量obj壓入棧stack；

pop（stack，ch）：從棧stack出棧一個元素并把該元素放到變量ch中，如果沒有帶參數(shù)ch，表示從棧stack出棧一個元素作為函數(shù)返回值；

strcat（obj1，obj2，obj3）：將3個變量obj1、obj2、obj3順序連接成一個字符串；

percede（ch）：獲得運(yùn)算符ch的優(yōu)先級；

gettop（stack）：從棧stack中獲得棧頂元素；

stacklength（stack）：返回棧stack中的元素個數(shù)；

dataobject（ch）：判斷變量ch是否為數(shù)據(jù)對象，如果是，則返回true，否則返回false；

stack_trans_prefix（stack1，stack2）：表示將一個表達(dá)式轉(zhuǎn)換為對應(yīng)的前綴表達(dá)式過程，從棧stack1中出棧一個元素，從棧stack2中出棧兩個元素，將出棧的3個元素連接成的一個前綴表達(dá)式變量，壓入棧stack2，具體運(yùn)算過程如下：

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）表示將一個表達(dá)式轉(zhuǎn)換為對應(yīng)的中綴表達(dá)式過程，從棧stack1中出棧一個元素，從棧stack2中出棧兩個元素，并將出棧的3個元素連接成的一個中綴表達(dá)式變量壓入棧stack2，具體運(yùn)算過程如下：

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）表示將一個表達(dá)式轉(zhuǎn)換為對應(yīng)的后綴表達(dá)式的過程，從棧stack1中出棧一個元素，從棧stack2中出棧兩個元素，并將出棧的3個元素連接成的一個后綴表達(dá)式變量壓入棧stack2，具體運(yùn)算過程如下：

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

注：后面的算法實(shí)現(xiàn)只給出主要部分，一些變量的初始化部分略去。

2.2由表達(dá)式獲得對應(yīng)的前綴表達(dá)式

2.2.1操作規(guī)則

由表達(dá)式獲得對應(yīng)前綴表達(dá)式的主要操作規(guī)則：將表達(dá)式的運(yùn)算符向前移動到參與運(yùn)算的兩個數(shù)據(jù)對象之前，這里的運(yùn)算符是普通的算術(shù)運(yùn)算符，不包括括號，對于括號需要成對進(jìn)行處理；數(shù)據(jù)對象可以是一個變量名，也可以是一個前綴表達(dá)式。在設(shè)計更為詳細(xì)的操作規(guī)則時，需要對運(yùn)算符的優(yōu)先級進(jìn)行判斷處理。

2.2.2算法實(shí)現(xiàn)

由表達(dá)式獲得對應(yīng)前綴表達(dá)式的算法實(shí)現(xiàn)需要借助兩個輔助棧stack_data和stack_symbol進(jìn)行。其中，stack_data棧中存放變量名或前綴表達(dá)式，stack_symbol棧用來存放運(yùn)算符，函數(shù)名為TransFromExptoPrefix，參數(shù)prefix表示最終得到的前綴表達(dá)式存放到數(shù)組的名稱。參數(shù)exp表示最初的表達(dá)式，其主要思想是每次遇到運(yùn)算符時，需要將該運(yùn)算符與棧stack_symbol中的運(yùn)算符進(jìn)行比較。如果該運(yùn)算符的優(yōu)先級比棧stack_symbol棧頂?shù)倪\(yùn)算符優(yōu)先級高，則將該運(yùn)算符壓入棧stack_symbol，否則從棧stack_symbol中出棧一個運(yùn)算符，從棧stack_data中出棧兩個數(shù)據(jù)對象，連接成一個前綴表達(dá)式壓入棧stack_data。將當(dāng)前運(yùn)算符壓入棧stack_symbol；每次遇到數(shù)據(jù)對象（即變量名）時將該變量壓入棧stack_data。函數(shù)表示過程如下：

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由表達(dá)式獲得對應(yīng)的后綴表達(dá)式

2.3.1操作規(guī)則

由表達(dá)式獲得對應(yīng)后綴表達(dá)式的主要操作規(guī)則：將表達(dá)式的運(yùn)算符向后移動到參與運(yùn)算的兩個數(shù)據(jù)對象之后，這里的運(yùn)算符是普通算術(shù)運(yùn)算符，不包括括號，對于括號的處理需要成對進(jìn)行；數(shù)據(jù)對象可以是一個變量名，也可以是一個后綴表達(dá)式。在設(shè)計更為詳細(xì)的操作規(guī)則時，需要對運(yùn)算符的優(yōu)先級進(jìn)行處理。

2.3.2算法實(shí)現(xiàn)

由表達(dá)式獲得對應(yīng)后綴表達(dá)式的算法實(shí)現(xiàn)需要借助兩個輔助棧stack_data和stack_symbol進(jìn)行。其中，stack_data棧中存放變量名或后綴表達(dá)式，stack_symbol棧用來存放運(yùn)算符，函數(shù)名為TransFromExptoPost，參數(shù)post表示最終得到的后綴表達(dá)式存放的數(shù)組名稱，參數(shù)exp表示最初的表達(dá)式。其主要思想是每次遇到運(yùn)算符時，需要將該運(yùn)算符與棧stack_symbol中棧頂?shù)倪\(yùn)算符進(jìn)行比較。如果該運(yùn)算符的優(yōu)先級比棧stack_symbol棧頂?shù)倪\(yùn)算符優(yōu)先級高，則將該運(yùn)算符壓入棧stack_symbol；否則，當(dāng)棧stack_symbol中棧頂元素運(yùn)算符優(yōu)先級大于等于當(dāng)前遇到的運(yùn)算符時，需要進(jìn)行以下處理：從棧stack_data中出棧兩個數(shù)據(jù)對象，從棧stack_symbol中出棧一個運(yùn)算符，連接成一個后綴表達(dá)式壓入棧stack_data，然后將當(dāng)前運(yùn)算符壓入棧stack_symbol；每次遇到數(shù)據(jù)對象（即變量名），則將該數(shù)據(jù)對象壓入棧stack_data。其函數(shù)表示過程如下：

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由前綴表達(dá)式獲得對應(yīng)的中綴表達(dá)式

2.4.1操作規(guī)則

由前綴表達(dá)式獲得對應(yīng)中綴表達(dá)式的操作規(guī)則：將前綴表達(dá)式的運(yùn)算符向后移動到參與運(yùn)算的兩個數(shù)據(jù)對象之間。這里所說的運(yùn)算符是普通的算術(shù)運(yùn)算符，沒有括號；數(shù)據(jù)對象可以是一個變量名，也可以是一個中綴表達(dá)式。由前綴表達(dá)式獲得對應(yīng)的中綴表達(dá)式不需要考慮運(yùn)算符的優(yōu)先級，只需要考慮運(yùn)算符出現(xiàn)的先后以及數(shù)據(jù)對象出現(xiàn)的位置。

2.4.2算法實(shí)現(xiàn)

由前綴表達(dá)式獲得對應(yīng)中綴表達(dá)式的算法實(shí)現(xiàn)需要借助兩個輔助棧stack_data和stack_symbol進(jìn)行。其中，stack_data棧中存放變量名或中綴表達(dá)式，stack_symbol棧用來存放運(yùn)算符，函數(shù)名為TransFromPrefixtoIn，參數(shù)in表示最終得到的中綴表達(dá)式存放的數(shù)組名稱，參數(shù)prefix表示最初的前綴表達(dá)式。其主要思想是每次遇到運(yùn)算符時，將運(yùn)算符壓入棧stack_symbol。每次遇到數(shù)據(jù)對象時判斷是否是連續(xù)的兩個對象，如果是，則將連續(xù)的兩個數(shù)據(jù)對象從棧stack_data中出棧，與棧stack_symbol出棧的運(yùn)算符結(jié)合為中綴表達(dá)式，然后壓入棧stack_data。為了判斷是否遇到了連續(xù)的兩個數(shù)據(jù)對象，需要在壓入第一個數(shù)據(jù)元素至棧stack_data時，壓入棧stack_symbol的一個特殊元素（'&'），表示數(shù)據(jù)對象中已經(jīng)出現(xiàn)了一個元素。其函數(shù)表示過程如下：

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由前綴表達(dá)式獲得對應(yīng)的后綴表達(dá)式

2.5.1操作規(guī)則

由前綴表達(dá)式獲得對應(yīng)后綴表達(dá)式的操作規(guī)則：將前綴表達(dá)式的運(yùn)算符向后移動到參與運(yùn)算的兩個數(shù)據(jù)對象之后。這里所說的運(yùn)算符是普通的算術(shù)運(yùn)算符，沒有括號；數(shù)據(jù)對象可以是一個變量名，也可以是一個后綴表達(dá)式。由前綴表達(dá)式獲得對應(yīng)的后綴表達(dá)式不需要考慮運(yùn)算符的優(yōu)先級，只需考慮運(yùn)算符出現(xiàn)的先后以及數(shù)據(jù)對象出現(xiàn)的位置。

2.5.2算法實(shí)現(xiàn)

由前綴表達(dá)式獲得對應(yīng)后綴表達(dá)式的算法實(shí)現(xiàn)需要借助兩個輔助棧stack_data和stack_symbol進(jìn)行。其中，stack_data棧中存放變量名或后綴表達(dá)式，stack_symbol棧用來存放運(yùn)算符，函數(shù)名為TransFromPrefixtoPost，參數(shù)post表示最終得到的后綴表達(dá)式存放的數(shù)組名稱，參數(shù)prefix表示最初的前綴表達(dá)式。其主要思想是每次遇到運(yùn)算符時，將運(yùn)算符壓入棧stack_symbol。每次遇到數(shù)據(jù)對象，將數(shù)據(jù)對象壓入棧stack_data，然后判斷是否是連續(xù)的兩個數(shù)據(jù)對象。如果是，則將連續(xù)的兩個數(shù)據(jù)對象從棧stack_data出棧與stack_symbol棧頂出棧運(yùn)算結(jié)合為后綴表達(dá)式，然后壓入棧stack_data，最后向棧stack_symbol壓入元素'&'。為了判斷是否遇到了連續(xù)的兩個數(shù)據(jù)對象，需要在壓入第一個數(shù)據(jù)元素至棧stack_data時，壓入棧stack_symbol一個特殊元素（'&'），表示數(shù)據(jù)對象中已經(jīng)出現(xiàn)了一個元素。其函數(shù)表示過程如下：

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由后綴表達(dá)式獲得對應(yīng)的前綴表達(dá)式

2.6.1操作規(guī)則

由后綴表達(dá)式獲得對應(yīng)前綴表達(dá)式的主要操作規(guī)則：將后綴表達(dá)式的運(yùn)算符向前移動到參與運(yùn)算的兩個數(shù)據(jù)對象之前。這里所說的運(yùn)算符是普通的算術(shù)運(yùn)算符，沒有括號；數(shù)據(jù)對象可以是一個變量名，也可以是一個前綴表達(dá)式。由后綴表達(dá)式獲得對應(yīng)的前綴表達(dá)式不需要考慮運(yùn)算符的優(yōu)先級，只需考慮運(yùn)算符出現(xiàn)的先后以及數(shù)據(jù)對象出現(xiàn)的位置。

2.6.2算法實(shí)現(xiàn)

由后綴表達(dá)式獲得對應(yīng)前綴表達(dá)式的算法實(shí)現(xiàn)需要借助一個輔助棧stack_data進(jìn)行。stack_data棧中用于存放變量名或前綴表達(dá)式，函數(shù)名為TransFromPosttoPrefix，參數(shù)prefix表示最終的前綴表達(dá)式存放的數(shù)組名稱，參數(shù)post表示最初的后綴表達(dá)式。其主要思想是每次遇到數(shù)據(jù)對象（即變量名）時，將該數(shù)據(jù)對象壓入棧stack_data，每次遇到運(yùn)算符，從棧stack_data出棧兩個數(shù)據(jù)對象并和該運(yùn)算符連接成前綴表達(dá)式，然后將該前綴表達(dá)式壓入棧stack_data。其函數(shù)表示過程如下：

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由后綴表達(dá)式獲得對應(yīng)的中綴表達(dá)式

2.7.1操作規(guī)則

由后綴表達(dá)式獲得對應(yīng)中綴表達(dá)式的主要操作規(guī)則：將后綴表達(dá)式的運(yùn)算符向前移動到參與運(yùn)算的兩個數(shù)據(jù)對象之間。這里所說的運(yùn)算符是普通的算術(shù)運(yùn)算符，沒有括號；數(shù)據(jù)對象可以是一個變量名，也可以是一個中綴表達(dá)式。由后綴表達(dá)式獲得對應(yīng)的中綴表達(dá)式不需要考慮運(yùn)算符的優(yōu)先級，只需考慮運(yùn)算符出現(xiàn)的先后以及數(shù)據(jù)對象出現(xiàn)的位置。

2.7.2算法實(shí)現(xiàn)

由后綴表達(dá)式獲得對應(yīng)中綴表達(dá)式的算法實(shí)現(xiàn)需要借助一個輔助棧stack_data進(jìn)行。stack_data棧中用于存放變量名或中綴表達(dá)式，函數(shù)名為TransFromPosttoIn，參數(shù)in表示最終得到的中綴表達(dá)式存放的數(shù)組名稱，參數(shù)post表示最初的后綴表達(dá)式。其主要思想是每次遇到數(shù)據(jù)對象（即變量名）時，將數(shù)據(jù)對象壓入棧stack_data，每次遇到運(yùn)算符，則從棧stack_data出棧兩個數(shù)據(jù)對象并和該運(yùn)算符連接成中綴表達(dá)式，然后將該中綴表達(dá)式壓入棧stack_data。其函數(shù)表示過程如下：

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案例分析

示例：對于表達(dá)式"（a+b）*（c-d）-（e+f）"，通過上面的算法實(shí)現(xiàn)過程可以得到其前綴表達(dá)式為：-*+ab-cd+ef，后綴表達(dá)式為：ab+cd-*ef+-，前綴表達(dá)式、中綴表達(dá)式和后綴表達(dá)式之間的相互轉(zhuǎn)換也可按照上面的算法實(shí)現(xiàn)過程分別得到，這里不再詳述。

3對應(yīng)二叉樹結(jié)構(gòu)建立

3.1算法準(zhǔn)備

為了后面算法表示方便，先對以下函數(shù)的含義進(jìn)行說明：

t=CreateNewNode（ch）：表示新建一個數(shù)據(jù)域?yàn)閏h且左、右孩子均為空的二叉樹結(jié)點(diǎn)，并將該結(jié)點(diǎn)的指針賦值給變量t；

stack_trans_tree（stack_symbol，stack_tree）：表示從stack_symbol出棧一個元素并以該元素為數(shù)據(jù)域建立一個二叉樹結(jié)點(diǎn)。從stack_tree出棧兩個元素，將新建立的二叉樹結(jié)點(diǎn)的左右兩個孩子分別指向這兩個元素，然后將該二叉樹結(jié)點(diǎn)指針壓入棧stack_tree，具體執(zhí)行過程如下：

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由表達(dá)式建立對應(yīng)的二叉樹結(jié)構(gòu)

3.2.1操作規(guī)則

由表達(dá)式建立對應(yīng)二叉樹結(jié)構(gòu)主要有兩種思路：①按照由表達(dá)式獲得對應(yīng)的前綴表達(dá)式進(jìn)行；②按照由表達(dá)式獲得對應(yīng)的后綴表達(dá)式進(jìn)行。這里以由表達(dá)式獲得對應(yīng)的后綴表達(dá)式思路設(shè)計操作規(guī)則：遇到運(yùn)算符，則按照運(yùn)算符優(yōu)先級判斷是否需要處理之前的運(yùn)算符，如果當(dāng)前運(yùn)算符的優(yōu)先級不大于之前的運(yùn)算符優(yōu)先級，則需要處理之前的運(yùn)算符。處理過程為：將之前的運(yùn)算符作為創(chuàng)建二叉樹結(jié)點(diǎn)的數(shù)據(jù)域，并將其左右指針指向最近處理好的二叉樹結(jié)構(gòu)，然后將該二叉樹結(jié)點(diǎn)指針作為最新出現(xiàn)的二叉樹結(jié)構(gòu)；如果遇到數(shù)據(jù)對象（即變量名），則以該數(shù)據(jù)對象作為數(shù)據(jù)域建立一個二叉樹結(jié)點(diǎn)并且其左右孩子均為空，以該二叉樹結(jié)點(diǎn)指針作為最新出現(xiàn)的二叉樹結(jié)構(gòu)。這里所說的運(yùn)算符包括對括號的處理，括號處理需要成對進(jìn)行；數(shù)據(jù)對象是一個以二叉樹結(jié)點(diǎn)指針為代表的二叉樹結(jié)構(gòu)。

3.2.2算法實(shí)現(xiàn)

由表達(dá)式建立對應(yīng)二叉樹結(jié)構(gòu)的算法實(shí)現(xiàn)可按照由表達(dá)式獲得對應(yīng)的前綴表達(dá)式思路進(jìn)行，也可按照由表達(dá)式獲得對應(yīng)的后綴表達(dá)式思路進(jìn)行，本文按由表達(dá)式獲得對應(yīng)的后綴表達(dá)式思路進(jìn)行。與由表達(dá)式獲得對應(yīng)的后綴表達(dá)式過程類似，需要借助兩個輔助棧stack_tree和stack_symbol進(jìn)行。其中，stack_tree棧中存放建立的二叉樹結(jié)點(diǎn)指針，stack_symbol棧用來存放運(yùn)算符，函數(shù)名為CreateBiTreeFromExp，參數(shù)T表示最終得到的二叉樹結(jié)構(gòu)的根結(jié)點(diǎn)指針，參數(shù)exp表示最初的表達(dá)式。其函數(shù)表示過程如下：

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由前綴表達(dá)式建立對應(yīng)的二叉樹結(jié)構(gòu)

3.3.1操作規(guī)則

由前綴表達(dá)式建立對應(yīng)二叉樹結(jié)構(gòu)主要操作規(guī)則：遇到數(shù)據(jù)對象（即變量名），則以該數(shù)據(jù)對象為數(shù)據(jù)域新建一個二叉樹結(jié)點(diǎn)結(jié)構(gòu)并其左右孩子均為空，然后判斷是否已經(jīng)連續(xù)兩次出現(xiàn)了數(shù)據(jù)對象。如果是，則將之前出現(xiàn)的運(yùn)算符為數(shù)據(jù)域創(chuàng)建二叉樹結(jié)點(diǎn)，并將其左右指針指向最近得到的兩個二叉樹結(jié)構(gòu)，然后將該二叉樹結(jié)點(diǎn)指針作為最新出現(xiàn)的二叉樹結(jié)構(gòu)；如果遇到運(yùn)算符則暫時不予處理。由前綴表達(dá)式建立對應(yīng)的二叉樹結(jié)構(gòu)，不需要考慮運(yùn)算符的優(yōu)先級，只需考慮運(yùn)算符出現(xiàn)先后以及數(shù)據(jù)對象出現(xiàn)的位置。

3.3.2算法實(shí)現(xiàn)

由前綴表達(dá)式建立對應(yīng)二叉樹結(jié)構(gòu)的算法實(shí)現(xiàn)需要借助兩個輔助棧stack_tree和stack_symbol進(jìn)行。其中，stack_tree棧中存放二叉樹結(jié)點(diǎn)指針，stack_symbol棧用來存放運(yùn)算符，函數(shù)名為CreateBiTreeFromPrefix，參數(shù)T表示最終得到的二叉樹結(jié)構(gòu)的根結(jié)點(diǎn)指針，參數(shù)prefix表示最初的前綴表達(dá)式。其主要思想是每次遇到運(yùn)算符時，將運(yùn)算符壓入棧stack_symbol，每次遇到數(shù)據(jù)對象（即變量名）則以該數(shù)據(jù)對象為數(shù)據(jù)域創(chuàng)建一個二叉樹結(jié)點(diǎn)，且其左、右孩子均為空并壓入棧stack_tree，然后判斷是否是出現(xiàn)了連續(xù)的兩個數(shù)據(jù)對象。如果是，則將連續(xù)的兩個數(shù)據(jù)對象建立的二叉樹結(jié)點(diǎn)作為以stack_symbol棧頂出棧運(yùn)算符作為數(shù)據(jù)域的二叉樹結(jié)點(diǎn)的左右孩子，然后將新建立的二叉樹結(jié)點(diǎn)指針壓入棧stack_tree。為了判斷是否出現(xiàn)了連續(xù)的兩個數(shù)據(jù)對象，需要在壓入第一個數(shù)據(jù)元素至棧stack_tree時，壓入棧stack_symbol一個特殊元素'&'，表示數(shù)據(jù)對象中已經(jīng)出現(xiàn)了一個元素。如果棧stack_symbol棧頂元素已經(jīng)是'&'則不進(jìn)行壓入。其函數(shù)表示過程如下：

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由后綴表達(dá)式建立對應(yīng)的二叉樹結(jié)構(gòu)

3.4.1操作規(guī)則

由后綴表達(dá)式獲得對應(yīng)二叉樹結(jié)構(gòu)的操作規(guī)則：遇到數(shù)據(jù)對象（即變量名），則以該數(shù)據(jù)對象為數(shù)據(jù)域新建一個二叉樹結(jié)點(diǎn)并且其左右孩子均為空，以該二叉樹結(jié)點(diǎn)指針作為最新出現(xiàn)的二叉樹結(jié)構(gòu)；如果遇到運(yùn)算符，則以該運(yùn)算符作為數(shù)據(jù)域新建一個二叉樹結(jié)點(diǎn)結(jié)構(gòu)，并將其左右孩子分別指向最近出現(xiàn)的兩個二叉樹結(jié)構(gòu)，然后將該二叉樹結(jié)點(diǎn)指針作為最近出現(xiàn)的二叉樹結(jié)構(gòu)。由后綴表達(dá)式獲得對應(yīng)的二叉樹結(jié)構(gòu)，不需要考慮運(yùn)算符的優(yōu)先級，只需要考慮運(yùn)算符出現(xiàn)的先后以及數(shù)據(jù)對象出現(xiàn)的位置。

3.4.2算法實(shí)現(xiàn)

由后綴表達(dá)式建立對應(yīng)二叉樹結(jié)構(gòu)的算法實(shí)現(xiàn)需要借助一個輔助棧stack_tree進(jìn)行。stack_tree棧中用于存放二叉樹結(jié)點(diǎn)指針為代表的二叉樹結(jié)構(gòu)，函數(shù)名為CreateBiTreeFromPost，參數(shù)T表示最終得到的二叉樹結(jié)構(gòu)的根結(jié)點(diǎn)指針，參數(shù)post表示最初的后綴表達(dá)式。其主要思想是每次遇到數(shù)據(jù)對象（即變量名），則以該數(shù)據(jù)對象為數(shù)據(jù)域創(chuàng)建一個二叉樹結(jié)點(diǎn)且其左、右孩子均為空，然后將其壓入棧stack_tree，每次遇到運(yùn)算符，則從棧stack_tree出棧兩個元素，然后以該運(yùn)算符為數(shù)據(jù)域新建一個二叉樹結(jié)點(diǎn)，并且其左右孩子指針指向出棧的兩個元素，然后將新建的二叉樹結(jié)點(diǎn)指針壓入棧stack_tree。其函數(shù)表示過程如下：

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案例分析

例：對于表達(dá)式"（a+b）*（c-d）-（e+f）"，通過上面的算法實(shí)現(xiàn)過程可以建立對應(yīng)的二叉樹結(jié)構(gòu)，如圖1所示。其詳細(xì)建立過程這里不再詳述。在建立二叉樹結(jié)構(gòu)的基礎(chǔ)上，其前序遍歷、中序遍歷、后序遍歷分別對應(yīng)前綴表達(dá)式、中綴表達(dá)式和后綴表達(dá)式。

4結(jié)語

對于棧的應(yīng)用，比較重要的一點(diǎn)就是在設(shè)計算法之前，需要弄清楚遇到不同情況時的操作規(guī)則，在弄清楚操作規(guī)則之后再設(shè)計好棧中需要存放元素的數(shù)據(jù)類型，然后按照操作規(guī)則確定相應(yīng)進(jìn)棧和出棧情況，以及進(jìn)棧和出棧之前及之后需要處理內(nèi)容。棧的應(yīng)用是數(shù)據(jù)結(jié)構(gòu)中非常重要的內(nèi)容，在遇到實(shí)際問題時需要先對問題進(jìn)行分析，判斷其需要哪種數(shù)據(jù)結(jié)構(gòu)解決，然后再按照該數(shù)據(jù)結(jié)構(gòu)特點(diǎn)進(jìn)行分析和處理。

參考文獻(xiàn)：

[1]湯巖，賈紅雨，紀(jì)賢標(biāo).條形裝箱問題的基于后綴表達(dá)式的混合遺傳算法[J].喀什師范學(xué)院學(xué)報，2007，28（3）：76-78.

[2]熊風(fēng)光，況立群，韓焱.可擴(kuò)展的邏輯表達(dá)式求值系統(tǒng)的設(shè)計與實(shí)現(xiàn)[J].計算機(jī)工程與設(shè)計，2012，33（10）：3858-3861.

[3]李良敏.遺傳編程的MATLAB語言實(shí)現(xiàn)[J].計算機(jī)工程，2005，31（13）：87-89.

[4]薛濤，刁明光，呂志成.巖石地球化學(xué)圖解輔助分析軟件的關(guān)鍵問題及解決方法[J].現(xiàn)代地質(zhì)，2013，27（6）：1316-1322.

[5]王煥宇.民用飛機(jī)機(jī)組告警系統(tǒng)試驗(yàn)室自動化測試技術(shù)研究[J].科技創(chuàng)新導(dǎo)報，2016，13（6）：7-10.

[6]張超超.可視化公式編輯軟件的設(shè)計與實(shí)現(xiàn)[J].科學(xué)與財富，2015（9）：94-97.

[7]郭群.逆波蘭式探微——后綴表達(dá)式的求法及其適用情況比較[J].黑龍江科技信息，2007（16）：36-36.

[8]李艷玲.數(shù)據(jù)結(jié)構(gòu)中實(shí)現(xiàn)表達(dá)式求值算法的巧妙轉(zhuǎn)換[J].職大學(xué)報，2005（4）：62-63.

[9]郭萌萌，許永昌.中綴及后綴算術(shù)表達(dá)式在運(yùn)算中的應(yīng)用研究[J].電腦知識與技術(shù)，2009，5（32）：8921-8923.

[10]周欣.逆波蘭式轉(zhuǎn)換規(guī)則的推導(dǎo)過程[J].電腦編程技巧與維護(hù)，2016（21）：35-36.

[11]顏晶晶，張濤.將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的三種方法[J].計算機(jī)與網(wǎng)絡(luò)，2004（16）：54-55.

[12]胡云，毛萬年.一種將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的新方法[J].成都大學(xué)學(xué)報：自然科學(xué)版，2008，27（1）：52-55.

[13]朱玉娟.論中綴表達(dá)式與后綴表達(dá)式的轉(zhuǎn)換[J].現(xiàn)代商貿(mào)工業(yè)，2008，20（6）：258-259.

[14]沈華.一種前綴表達(dá)式直接轉(zhuǎn)換為后綴表達(dá)式的算法[J].電腦編程技巧與維護(hù)，2013（2）：12-14.

[15]曹曉麗，潘穎.一種利用棧實(shí)現(xiàn)中綴表達(dá)式向前綴表達(dá)式轉(zhuǎn)換方法的改進(jìn)[J].甘肅科技，2006，22（11）：64-66.

[16]李世華，劉曉娟，姜晨，等.關(guān)于表達(dá)式求值的算法研究與實(shí)現(xiàn)[J].甘肅科技，2011，27（1）：11-15.

[17]肖巍.基于C#的表達(dá)式解析器設(shè)計方法[J].長春教育學(xué)院學(xué)報，2010，26（6）：125-126.

[18]李橙，丁國棟.棧在表達(dá)式求值中的應(yīng)用[J].電腦知識與技術(shù)，2014（34）：8156-8157.

[19]錢學(xué)林.算術(shù)表達(dá)式計算的實(shí)現(xiàn)[J].電子世界，2014（4）：167-170.

[20]王若民.后綴表達(dá)式及其多位數(shù)的算術(shù)運(yùn)算探析[J].科教文匯，2007（30）：215-216.

（責(zé)任編輯：杜能鋼）