基于二叉樹的將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式的方法

2012-01-10 03:35:34胡云

成都大學(xué)學(xué)報(bào)(自然科學(xué)版) 2012年3期

胡云

(無錫廣播電視大學(xué),江蘇無錫 214011)

0 引言

運(yùn)算符和運(yùn)算對象是表達(dá)式的兩個組成部分,根據(jù)運(yùn)算符計(jì)算對象的數(shù)量將其分為單目運(yùn)算符、雙目運(yùn)算符和三目運(yùn)算符[1-3].為便于理解,本研究僅討論由雙目運(yùn)算符構(gòu)成的表達(dá)式.根據(jù)運(yùn)算符和運(yùn)算對象的相對位置關(guān)系可以將表達(dá)式分為前綴表達(dá)式、中綴表達(dá)式和后綴表達(dá)式.實(shí)際應(yīng)用中,使用頻率最高的是中綴表達(dá)式,其運(yùn)算符的兩個運(yùn)算對象一個置于前面,另一個置于后面.人們習(xí)慣使用這種表達(dá)式形式,直觀上求值也相對容易,但在計(jì)算機(jī)上對其求值,因?yàn)橥瑫r要考慮運(yùn)算符的優(yōu)先級和結(jié)合性,就顯得比較困難.對此,本研究提出一種基于二叉樹的轉(zhuǎn)換方法.

1 傳統(tǒng)的轉(zhuǎn)換方法

通常,將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式的方法是:把每個運(yùn)算符的兩個運(yùn)算對象都移到它的后面,然后去除掉所有的括號.因此在前綴表達(dá)式中,沒有括號運(yùn)算符,也沒有優(yōu)先級的差別.本研究討論的運(yùn)算符及其優(yōu)先級如表1所示.

表1 各個算術(shù)運(yùn)算符的優(yōu)先級

表1中,osp稱為棧外優(yōu)先級,isp稱為棧內(nèi)優(yōu)先級.右括號′)′具有最高的棧外優(yōu)先級,處理時一遇到′)′立即將其壓入棧內(nèi),進(jìn)棧后,其棧內(nèi)優(yōu)先級變得很低,僅高于′#′,其目的是便于括號內(nèi)的其它運(yùn)算符進(jìn)棧.其它運(yùn)算符進(jìn)棧后優(yōu)先級數(shù)都減1.運(yùn)算符優(yōu)先級相等的情況只出現(xiàn)在括號匹配或棧底的′#′號與輸入流最后的′#′號匹配時.前者將連續(xù)彈出位于棧頂?shù)倪\(yùn)算符,直至遇到′)′為止.然后將′)′退棧以成對消除括號,后者將結(jié)束算法.

轉(zhuǎn)換后,表達(dá)式中運(yùn)算對象的次序不變,而運(yùn)算符的次序發(fā)生了變化,由處在兩個操作對象的中間變?yōu)樘幵趦蓚€運(yùn)算對象的前面,同時去掉了所有的括號.轉(zhuǎn)換過程使用兩個棧,一個用來存放運(yùn)算符,另一個用來保存轉(zhuǎn)換得到的結(jié)果.對于存放運(yùn)算符的棧,先要在棧底放一個特殊運(yùn)算符,假定為′#′字符,讓它具有最低的運(yùn)算符優(yōu)先級,假定為數(shù)值0.對中綴表達(dá)式字符串的掃描是從后向前進(jìn)行的.

算法具體描述如下:

(1)運(yùn)算符棧R和保存結(jié)果的棧D初始化,將結(jié)束符′#′壓入棧R,然后讀入中綴表達(dá)式字符串的最后一個字符ch.

(2)重復(fù)執(zhí)行以下步驟,直到第一個字符:①若ch是運(yùn)算對象直接壓入棧D,讀入前一個字符到ch.②若ch是運(yùn)算符,判斷ch的優(yōu)先級osp和棧R的棧頂運(yùn)算符op的優(yōu)先級isp:若osp(ch)>isp(op),將ch壓入棧R,讀入前一個字符到ch;若osp(ch)< isp(op),將棧R出棧的元素壓入到棧D中,繼續(xù)執(zhí)行步驟②;若osp(ch)=isp(op),說明ch是字符′(′,對棧R執(zhí)行退棧操作,讀入前一個字符到ch.

(3)將棧R中各個元素依次出棧,再壓入到棧D中,直到出棧元素是字符′#′,然后將棧D各個元素依次出棧輸出,即得到轉(zhuǎn)換后的前綴表達(dá)式.

設(shè)以′#′字符作為結(jié)束符的中綴表達(dá)式已經(jīng)保存在s1字符串中,轉(zhuǎn)換后得到的前綴表達(dá)式存于s2字符串中.由中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式的規(guī)則可知:為了使轉(zhuǎn)換正確,需要設(shè)定2個棧.

將字符串s1表示的中綴表達(dá)式轉(zhuǎn)為前綴表達(dá)式算法的基本操作方法是,從后向前掃描中綴表達(dá)式中的每個字符,對不同類型的字符分別進(jìn)行處理.設(shè)定一個標(biāo)識flag,如果掃描到的是非數(shù)值字符則將flag置為0;如掃描到的是數(shù)值字符則將flag置為1.設(shè)定2個棧,一個是存放運(yùn)算符的棧R,另一個是保存轉(zhuǎn)換結(jié)果的棧D.如果掃描到的是空格,則看成分隔符,無需進(jìn)行處理;若掃描到的是右括號,則將其壓入棧R中,等到以它為結(jié)束符的括號內(nèi)的表達(dá)式轉(zhuǎn)換完畢后再彈出棧,同時將flag置為0;若掃描到的是左括號,則說明括號內(nèi)的中綴表達(dá)式已經(jīng)轉(zhuǎn)換結(jié)束,將棧R中從棧頂直到對應(yīng)右括號之間的運(yùn)算符依次出棧并壓入棧D內(nèi),同時將flag置為0;若掃描到的是運(yùn)算符,并且該運(yùn)算符的優(yōu)先級不小于棧R的棧頂運(yùn)算符的優(yōu)先級時,將它壓入棧R內(nèi),同時將flag置為0;若掃描到的運(yùn)算符的優(yōu)先級小于棧R的棧頂運(yùn)算符的優(yōu)先級時,將棧R的棧頂運(yùn)算符出棧并壓入棧D中,直到棧R的棧頂運(yùn)算符的優(yōu)先級大于或等于當(dāng)前運(yùn)算符的優(yōu)先級為止,然后將運(yùn)算符壓入棧R內(nèi),同時將flag置為0;當(dāng)中綴表達(dá)式字符串掃描結(jié)束時將棧R中剩余的所有元素依次出棧并壓入棧D內(nèi),最后將棧D中元素依次出棧保存在字符串s2中,再向s2末尾加上表達(dá)式結(jié)束符′#′和字符串結(jié)束符′

基于二叉樹的將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式的方法

0 引 言

1 傳統(tǒng)的轉(zhuǎn)換方法

0 引言