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

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

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