計(jì)算機(jī)編程中的不等式作業(yè)表的求值

計(jì)算機(jī)編程中的不等式作業(yè)表的求值

表達(dá)方法是句子語(yǔ)言編譯中最基本的問(wèn)題。通常書(shū)寫(xiě)的算術(shù)表達(dá)式是由操作數(shù)和運(yùn)算符以及改變運(yùn)算次序的圓括號(hào)連接而成的式子。運(yùn)算符包括單目運(yùn)算符和雙目運(yùn)算符兩類(lèi),單目運(yùn)算符只要求一個(gè)操作數(shù),并被置于該操作數(shù)的前面,雙目運(yùn)算符要求有兩個(gè)操作數(shù),其位置因表示方法不同而有所差異。按照運(yùn)算符與運(yùn)算對(duì)象的位置關(guān)系,算術(shù)表達(dá)式的表示方法分為前綴表達(dá)式、中綴表達(dá)式和后綴表達(dá)式三種,其中后兩者較為常用。為了簡(jiǎn)便起見(jiàn),在本文的討論中只考慮雙目運(yùn)算符(僅+、-、*、/四種)以及括號(hào)。1運(yùn)算符的轉(zhuǎn)換中綴算術(shù)表達(dá)式最為常見(jiàn),其雙目運(yùn)算符置于與之相關(guān)的兩個(gè)運(yùn)算對(duì)象之間。對(duì)中綴表達(dá)式的求值,并非按照運(yùn)算符出現(xiàn)的自然順序來(lái)執(zhí)行其中的各個(gè)運(yùn)算,而是根據(jù)算符間的優(yōu)先關(guān)系來(lái)確定運(yùn)算的次序,此外,還需要顧及括號(hào)規(guī)則。中綴表達(dá)式的計(jì)算比較復(fù)雜,它必須遵守以下三條規(guī)則:1)先計(jì)算括號(hào)內(nèi),后計(jì)算括號(hào)外;2)在無(wú)括號(hào)或同層括號(hào)內(nèi),先乘除運(yùn)算,后加減運(yùn)算,即乘除運(yùn)算的優(yōu)先級(jí)高于加減運(yùn)算的優(yōu)先級(jí);3)同一優(yōu)先級(jí)運(yùn)算,從左向右依次進(jìn)行。從以上規(guī)則可以看出,在中綴表達(dá)式的計(jì)算過(guò)程中,既要考慮括號(hào)的作用,又要考慮運(yùn)算符的優(yōu)先級(jí),還要考慮運(yùn)算符出現(xiàn)的先后次序。因此,各運(yùn)算符實(shí)際的運(yùn)算次序往往同它們?cè)诒磉_(dá)式中出現(xiàn)的先后次序是不一致的,是不可預(yù)測(cè)的。中綴算術(shù)表達(dá)式符合人的思維方式,我們憑直觀判別一個(gè)中綴表達(dá)式中運(yùn)算符運(yùn)算順序并不困難,但對(duì)于計(jì)算機(jī)處理起來(lái)就比較復(fù)雜了。由于傳統(tǒng)計(jì)算機(jī)一維的計(jì)算模型,只能一個(gè)字符一個(gè)字符地掃描,要想確定哪一個(gè)運(yùn)算符優(yōu)先計(jì)算,就必須對(duì)整個(gè)中綴表達(dá)式掃描一遍,一個(gè)中綴表達(dá)式中有多少個(gè)運(yùn)算符,原則上就需要掃描多少遍才能計(jì)算完畢,這樣算法的時(shí)間復(fù)雜性就差了,顯然是不可取的。那么,能否把中綴算術(shù)表達(dá)式轉(zhuǎn)換成另一種形式的算術(shù)表達(dá)式,使計(jì)算簡(jiǎn)單化呢?回答是肯定的。波蘭科學(xué)家盧卡謝維奇(JLukasiewicz)很早就提出了算術(shù)表達(dá)式的另一種表示,即后綴表示,又稱(chēng)逆波蘭式,其定義是把運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象的后面。采用后綴表示的算術(shù)表達(dá)式被稱(chēng)為后綴算術(shù)表達(dá)式或后綴表達(dá)式。在后綴表達(dá)式中,不存在括號(hào),也不存在優(yōu)先級(jí)的差別,計(jì)算過(guò)程完全按照運(yùn)算符出現(xiàn)的先后次序進(jìn)行,整個(gè)計(jì)算過(guò)程僅需掃描一遍表達(dá)式便可完成,顯然比中綴表達(dá)式的計(jì)算要簡(jiǎn)單得多。例如,對(duì)于后綴表達(dá)式“12◆4◆–◆5◆/”,其中‘◆’字符表示成分之間的空格,因減法運(yùn)算符在前,除法運(yùn)算符在后,所以應(yīng)先做減法,后做除法;減法的兩個(gè)操作數(shù)是它前面的12和4,其中第一個(gè)數(shù)12是被減數(shù),第二個(gè)數(shù)4是減數(shù);除法的兩個(gè)操作數(shù)是它前面的12減4的差(即8)和5,其中8是被除數(shù),5是除數(shù)。那么中綴算術(shù)表達(dá)式轉(zhuǎn)換成對(duì)應(yīng)的后綴算術(shù)表達(dá)式的基本思想是什么呢?其實(shí)很簡(jiǎn)單,就是把每個(gè)運(yùn)算符都移到它的兩個(gè)運(yùn)算對(duì)象之后,而后刪除掉所有的括號(hào)即可。實(shí)際上J.Lukasiewicz最先提出的是表達(dá)式的前綴表示方法,即把每一個(gè)運(yùn)算符置于運(yùn)算對(duì)象之前,例如表達(dá)式“10+(20-5*3)(13-8)”其前綴表示形式為“+10/-20*53-138”。前綴表達(dá)式的優(yōu)點(diǎn)與后綴表達(dá)式的相同,也不含有括號(hào),表達(dá)式中的運(yùn)算也是按照運(yùn)算符出現(xiàn)的順序進(jìn)行的,計(jì)算也很容易實(shí)現(xiàn)。但由于其表示方法與人們的習(xí)慣相差甚遠(yuǎn),因而并不常用。對(duì)于簡(jiǎn)單的中綴表達(dá)式我們很容易得到其后綴表達(dá)式,但對(duì)于較為復(fù)雜的中綴表達(dá)式就很難從直觀上得到其后綴表達(dá)式。我們可以用一棵二叉樹(shù)來(lái)表示算術(shù)表達(dá)式,非終端結(jié)點(diǎn)表示運(yùn)算符,終端(葉子)結(jié)點(diǎn)代表運(yùn)算對(duì)象,如10+(20-5*3)/(13-8),那么按照先序、中序、后序遍歷二叉樹(shù),就可以分別得到前綴、中綴和后綴算術(shù)表達(dá)式。如此可以很方便地實(shí)現(xiàn)三種算術(shù)表達(dá)式的相互轉(zhuǎn)換。用計(jì)算機(jī)又是怎樣實(shí)現(xiàn)它們之間的轉(zhuǎn)化的呢?以下是自然語(yǔ)言描述的表達(dá)式轉(zhuǎn)前綴算法:1)求輸入串的逆序。2)檢查輸入的下一元素。3)假若是操作數(shù),把它添加到輸出串中。繼續(xù)輸入下一個(gè)字符。4)假若是閉括號(hào)(‘)’),將其入棧。繼續(xù)輸入下一個(gè)字符。5)假如是運(yùn)算符,則①假如?？?此運(yùn)算符入棧。繼續(xù)輸入下一個(gè)字符。②假如棧頂是閉括號(hào),此運(yùn)算符入棧。繼續(xù)輸入下一個(gè)字符。③假如它的優(yōu)先級(jí)高于或等于棧頂運(yùn)算符,此運(yùn)算符入棧。繼續(xù)輸入下一個(gè)字符。④否則,棧頂運(yùn)算符出棧并添加到輸出串中,重復(fù)步驟5)。6)假如是開(kāi)括號(hào)(‘(’),棧中運(yùn)算符逐個(gè)出棧并輸出,直到遇到閉括號(hào)。閉括號(hào)出棧并丟棄。繼續(xù)輸入下一個(gè)字符。7)假如輸入還未完畢,跳轉(zhuǎn)到步驟2)。8)假如輸入完畢,棧中剩余的所有操作符出棧并加到輸出串中。9)求輸出串的逆序。假設(shè)我們要將表達(dá)式“2*3/(2-1)+5*(4-1)”轉(zhuǎn)換成前綴形式,原表達(dá)式的逆序是“)1-4(*5+)1-2(/3*2”,輸出串的逆序?yàn)椤?/*23-21*5-41”,所以,最終求得的前綴表達(dá)式是“+/*23-21*5-41”。2u3000約束后的后ue在計(jì)算機(jī)中進(jìn)行算術(shù)表達(dá)式的求值是通過(guò)堆棧來(lái)實(shí)現(xiàn)的。后綴表達(dá)式由于其本身所具有的優(yōu)點(diǎn),表達(dá)式中各個(gè)運(yùn)算是按照運(yùn)算符出現(xiàn)的順序進(jìn)行的,其計(jì)算求值比較簡(jiǎn)單,掃描一遍即可完成。它只需要使用一個(gè)棧,用來(lái)存儲(chǔ)后綴表達(dá)式中的操作數(shù)、計(jì)算過(guò)程中的中間數(shù)據(jù)以及最后結(jié)果。而具體的求值比較簡(jiǎn)單,掃描一遍即可完成。它需要使用一個(gè)棧,假定用S表示,其元素類(lèi)型應(yīng)為操作數(shù)的類(lèi)型,假定為整型int,用此棧存儲(chǔ)后綴表達(dá)式中的操作數(shù)、計(jì)算過(guò)程中的中間數(shù)據(jù)以及最后結(jié)果。假定一個(gè)后綴算術(shù)表達(dá)式以字符‘$’作為結(jié)束符,并且以一個(gè)字符串的方式提供。后綴表達(dá)式求值算法的基本思路是:把包含后綴算術(shù)表達(dá)式的字符串定義為一個(gè)輸入字符串流對(duì)象,每次從中讀入一個(gè)字符(空格作為數(shù)據(jù)之間的分隔符,不會(huì)被作為字符讀入)時(shí),若是運(yùn)算符,則表明它的兩個(gè)操作數(shù)已經(jīng)在棧S中,其中棧頂元素為運(yùn)算符的后一個(gè)操作數(shù),棧頂元素的下一個(gè)元素為運(yùn)算符的前一個(gè)操作數(shù),把它們出棧后進(jìn)行相應(yīng)運(yùn)算即可,然后把運(yùn)算結(jié)果再壓入棧S中;否則,讀入的字符必為操作數(shù)的最高位數(shù)字,應(yīng)把它重新送回輸入流中,然后把下一個(gè)數(shù)據(jù)作為整型數(shù)據(jù)輸入,并將其壓入棧S中。依次掃描每一個(gè)字符(對(duì)于整型數(shù)據(jù)僅需掃描它的最高位并一次輸入整個(gè)數(shù)值)并進(jìn)行上述處理,直到遇到結(jié)束符‘$’為止,表明后綴表達(dá)式計(jì)算完畢,最終結(jié)果保存在棧中,并且棧中僅存這一個(gè)值,把它彈出返回即可。用類(lèi)C++語(yǔ)言描述的表達(dá)式后綴表達(dá)式求值的算法如下所述:3算的時(shí)間復(fù)雜性從兩個(gè)算法的分析比較中,我們可以看到優(yōu)先級(jí)的比較、運(yùn)算不按順序進(jìn)行使中綴表達(dá)計(jì)算的時(shí)間復(fù)雜性從O(n)到O(n2),花費(fèi)了大量的運(yùn)行時(shí)間。若在計(jì)算機(jī)上具體運(yùn)行,從中我們還會(huì)發(fā)現(xiàn),后綴表達(dá)式運(yùn)算時(shí)間比較穩(wěn)定,而中綴表達(dá)式由于運(yùn)算順序不同運(yùn)行時(shí)間相差較大,可見(jiàn)在時(shí)間復(fù)雜度和效率方面后綴表示方法要明顯優(yōu)于中綴表示方法。4算符優(yōu)先算法的計(jì)算方法經(jīng)以上的分析比較可以發(fā)現(xiàn),后綴表達(dá)式要優(yōu)于中綴表達(dá)式,非常適合用計(jì)算機(jī)求解。但是比起中綴表達(dá)式,后綴表達(dá)式在形式上沒(méi)有中綴表達(dá)直觀,后者更適于人類(lèi)的思維方式。因此利用計(jì)算機(jī)進(jìn)行科學(xué)計(jì)算,在高級(jí)語(yǔ)言程序設(shè)計(jì)中我們用中綴表達(dá)式來(lái)表示,而在計(jì)算機(jī)內(nèi)部是用后綴表達(dá)式來(lái)進(jìn)行計(jì)算的,因此為了處理方便,編譯程序常把中綴表達(dá)式首先轉(zhuǎn)換為后綴表達(dá)式然后再進(jìn)行運(yùn)算。中綴表達(dá)式與后綴表達(dá)式轉(zhuǎn)換算法的思想與中綴表達(dá)式求值算法基本相似,這里就不再贅述。但值得一提的是,轉(zhuǎn)換的時(shí)間復(fù)雜度是O(n)的,且只需要一個(gè)O(n/2)的運(yùn)算符棧。利用表達(dá)式的后綴表示和堆棧技術(shù)只需要兩遍掃描就可完成中綴算術(shù)表達(dá)式的計(jì)算,時(shí)間復(fù)雜度依然是O(n)的,顯然要大大優(yōu)于直接進(jìn)行中綴算術(shù)表達(dá)式計(jì)算。此算法的運(yùn)行時(shí)間主要用在while循環(huán)上,它從頭至尾掃描后綴表達(dá)式中的每一個(gè)數(shù)據(jù)(每個(gè)操作數(shù)或運(yùn)算符均為一個(gè)數(shù)據(jù)),若后綴表達(dá)式由n個(gè)數(shù)據(jù)組成,則此算法的時(shí)間復(fù)雜度為O(n)。此算法在運(yùn)行時(shí)所占用的臨時(shí)空間主要取決于操作數(shù)棧的大小,顯然,它的最大深度不會(huì)超過(guò)表達(dá)式中操作數(shù)的個(gè)數(shù),因?yàn)椴僮鲾?shù)的個(gè)數(shù)與運(yùn)算符(假定把‘$’也看作為一個(gè)特殊運(yùn)算符,即結(jié)束運(yùn)算符)的個(gè)數(shù)相等,所以此算法的空間復(fù)雜度也同樣為O(n)。中綴表達(dá)式求值同樣也可以用堆棧來(lái)實(shí)現(xiàn),但實(shí)現(xiàn)相對(duì)于后綴表達(dá)式較為復(fù)雜,它采用一種稱(chēng)為“算符優(yōu)先法”的算法,它必須嚴(yán)格按照前面所述的三條規(guī)則來(lái)進(jìn)行計(jì)算。為了實(shí)現(xiàn)算符優(yōu)先算法,要使用兩個(gè)工作棧。一個(gè)稱(chēng)為OPTR,用以寄存運(yùn)算符;另一個(gè)稱(chēng)為OPND,用以寄存操作數(shù)或運(yùn)算結(jié)果,它的基本思想較后綴表達(dá)式計(jì)算的不同在于:當(dāng)讀取到運(yùn)算符時(shí)并不可能作相應(yīng)運(yùn)算,必須首先比較運(yùn)算符棧中棧頂元素與當(dāng)前運(yùn)算符的優(yōu)先級(jí)。若為‘<’則運(yùn)算符入棧;若為‘=’則說(shuō)明