用兩種方式實現(xiàn)表達(dá)式自動計算

1、用兩種方式實現(xiàn)表達(dá)式自動計算- 1 -數(shù)據(jù)結(jié)構(gòu)（雙語） 數(shù)據(jù)結(jié)構(gòu)（雙語）——項目文檔報告 項目文檔報告用兩種方式實現(xiàn)表達(dá)式自動計算 用兩種方式實現(xiàn)表達(dá)式自動計算專 業(yè)： 業(yè)： 計算機科學(xué)與技術(shù)應(yīng)用 計算機科學(xué)與技術(shù)應(yīng)用 班 級： 級： 指導(dǎo)教師： 指導(dǎo)教師： 吳亞峰 吳亞峰 姓 名： 名：

2、學(xué) 號： 號： 用兩種方式實現(xiàn)表達(dá)式自動計算- 3 -一、設(shè)計思想 一、設(shè)計思想A: 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的設(shè)計思想：我們借助計算機計算一個算數(shù)表達(dá)式的值，而在計算機中，算術(shù)表達(dá)式是由常量，變量，運算符和括號組成。由于運算符的優(yōu)先級不同又要考慮括號。所以表達(dá)式不可能嚴(yán)格的從左到右進(jìn)行，因此我們借助棧和數(shù)組來實現(xiàn)表達(dá)式的求值。棧分別用來存儲操作數(shù)和運算符。在計算表達(dá)式的值之前，首先要把有括號的表

3、達(dá)式轉(zhuǎn)換成與其等值的無括號的表達(dá)式，也就是通常說的中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式。在這個過程中，要設(shè)計兩個棧，一個浮點型的存儲操作數(shù)，用以對無符號的表達(dá)式進(jìn)行求值。另一個字符型的用來存儲運算符，用以將算術(shù)表達(dá)式變成無括號的表達(dá)式；我們要假設(shè)運算符的優(yōu)先級：( ) , * /, + - 。首先將一標(biāo)識號‘#’入棧，作為棧底元素；接著從左到右對算術(shù)表達(dá)式進(jìn)行掃描。每次讀一個字符，若遇到左括號‘（’ ，則進(jìn)棧；若遇到的是操作數(shù)，則立即輸出；若又遇到

4、運算符，如果它的優(yōu)先級比棧頂元素的優(yōu)先級數(shù)高的話，則直接進(jìn)棧，否則輸出棧頂元素，直到新的棧頂元素的優(yōu)先級數(shù)比它低的，然后將它壓棧；若遇到是右括號‘） ’ ，則將棧頂?shù)倪\算符輸出，直到棧頂?shù)脑貫椤ā?，然后，左右括號互相底消；如果我們設(shè)計掃描到‘#’的時候表示表達(dá)式已經(jīng)掃描完畢，表達(dá)式已經(jīng)全部輸入，將棧中的運算符全部輸出，刪除棧底的標(biāo)識號。以上完成了中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式，輸出無括號的表達(dá)式，若遇數(shù)值，操作數(shù)進(jìn)棧；若遇運算符，讓操作數(shù)

5、棧的棧頂和次棧頂依次出棧并與此運算符進(jìn)行運算，運算結(jié)果入操作數(shù)棧；重復(fù)以上的步驟，直到遇到‘#’ ，則此時棧中的結(jié)果便是所求的后綴表達(dá)式的值，接著輸出結(jié)果。以上就是設(shè)計這個算法的主要的思想。設(shè)計思想的流程圖詳見圖 A；B: 直接計算表達(dá)式的值。所謂的掃一遍就是當(dāng)掃完一個表達(dá)式結(jié)果也就計算出來了，是在上面掃兩遍的思想進(jìn)行修改的得來，首先，我們要建立兩個棧，一個為字符型的用來存放運算符，另一個浮點型的用來存放操作數(shù)。我們開始對表達(dá)式進(jìn)行掃描

6、，首先我們要假設(shè)運算符的優(yōu)先級：( ) , * /, + - 。如果掃描到的是數(shù)字符號，把它們轉(zhuǎn)換成浮點型數(shù)據(jù)，存入操作數(shù)棧中。如果掃描到的是運算符號，第一個運算符進(jìn)棧，遇到‘（’存入運算符棧中，我們按照第一種算法的方法將表達(dá)式依次掃描。只不過不同的是，當(dāng)每取得的一個運算符的時候，都要與棧頂?shù)倪\算符進(jìn)行比較，如果它的優(yōu)先級小于棧頂運算符優(yōu)先級時，取出棧頂運算符并從操作數(shù)棧中取棧頂兩個數(shù)進(jìn)行運算，得到的結(jié)果則要存回操作數(shù)棧，就這樣邊掃描