用兩種方式實(shí)現(xiàn)表達(dá)式自動(dòng)計(jì)算

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

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

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

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

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

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