數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---用兩種方式實(shí)現(xiàn)表達(dá)式自動(dòng)計(jì)算

1、用兩種方式實(shí)現(xiàn)表達(dá)式自動(dòng)計(jì)算- 1 -一、設(shè)計(jì)思想 一、設(shè)計(jì)思想（一）中綴轉(zhuǎn)后綴的設(shè)計(jì)思想設(shè)計(jì)一個(gè)能實(shí)現(xiàn)表達(dá)式自動(dòng)求值計(jì)算，算術(shù)表達(dá)式由操作數(shù)、算符和括號(hào)組成。由于運(yùn)算符的優(yōu)先級(jí)不同還要考慮括號(hào)。所以表達(dá)式不可能一直的從左到右進(jìn)行，所以就借助棧來實(shí)現(xiàn)這個(gè)表達(dá)式的求值。首先要把算術(shù)表達(dá)式變換成與之等值的無括號(hào)表達(dá)式，也就是中綴轉(zhuǎn)后綴，它也是這個(gè)算法的關(guān)鍵。設(shè)計(jì)兩個(gè)棧，一個(gè)為字符型的，存放運(yùn)算符，用以將算術(shù)表達(dá)式變成無括號(hào)的表達(dá)式；另一個(gè)浮

2、點(diǎn)型的，存放操作數(shù)，用以對(duì)無符號(hào)的表達(dá)式進(jìn)行求值。我們要假設(shè)運(yùn)算符的優(yōu)先級(jí)：( ) , * /, + - 。首先將一左括號(hào)‘(’入棧，作為棧底元素；接著從左到右對(duì)算術(shù)表達(dá)式進(jìn)行掃描。每次讀一位，若遇到左括號(hào)‘（’ ，則進(jìn)棧；若遇到的是操作數(shù)，則立即輸出；若又遇到運(yùn)算符，如果它的優(yōu)先級(jí)比棧頂元素的優(yōu)先級(jí)數(shù)高的話，則直接進(jìn)棧，否則輸出棧頂元素，直到新的棧頂元素的優(yōu)先級(jí)數(shù)比它低的，然后將它壓棧；若遇到是右括號(hào)‘） ’ ，則將棧頂?shù)倪\(yùn)算符輸出

3、，直到棧頂?shù)脑貫椤ā?，然后，左右括號(hào)互相底消；到設(shè)計(jì)的結(jié)束標(biāo)志的時(shí)候表示表達(dá)式已經(jīng)掃描完畢，表達(dá)式已經(jīng)全部輸入，將棧中的運(yùn)算符全部輸出，刪除棧底的左括號(hào)。以上完成了中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式，輸出無括號(hào)的后綴表達(dá)式。讀后綴表達(dá)式，若遇數(shù)值，操作數(shù)進(jìn)棧；若遇運(yùn)算符，讓操作數(shù)棧的棧頂和次棧頂依次出棧并與此運(yùn)算符進(jìn)行運(yùn)算，運(yùn)算結(jié)果入操作數(shù)棧；重復(fù)這個(gè)步驟，直到遇到結(jié)束標(biāo)志，則此時(shí)棧中的結(jié)果便是所求的后綴表達(dá)式的值，接著輸出結(jié)果。以上就是設(shè)計(jì)

4、這個(gè)算法的主要的思想。(二) 直接計(jì)算的設(shè)計(jì)思想直接計(jì)算其實(shí)跟上一個(gè)相似，它是在上面掃兩遍的思想進(jìn)行修改的得來。首先，要建立兩個(gè)棧，一個(gè)為字符型的，存放運(yùn)算符，另一個(gè)浮點(diǎn)型的，存放操作數(shù)，我們開始對(duì)表達(dá)式進(jìn)行掃描。首先要確定運(yùn)算符的優(yōu)先級(jí)：（、 ） 、*、/、+、-。如果掃描到的是數(shù)字符號(hào)，把它們轉(zhuǎn)換成浮點(diǎn)型數(shù)據(jù)或其他可運(yùn)算的數(shù)據(jù)類型，存入操作數(shù)棧中。如果掃描到的是運(yùn)算符號(hào)，第一個(gè)運(yùn)算符進(jìn)棧，遇到‘（’存入運(yùn)算符棧中，我們按照第一種算法

5、的方法將表達(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ù)棧，就這樣邊掃描邊比較，再進(jìn)行計(jì)算。遇到“） ”對(duì)運(yùn)算符的處理相同。掃描結(jié)束后，把運(yùn)算符棧的元素和操作數(shù)棧里的數(shù)進(jìn)行運(yùn)算。每次的運(yùn)算結(jié)果再放入操作數(shù)棧，一直到計(jì)算到運(yùn)算符?？?。最后操作數(shù)棧的棧頂留下的操作數(shù)即表達(dá)式的計(jì)算結(jié)果。以上就

6、是直接計(jì)算表達(dá)式的思路。用兩種方式實(shí)現(xiàn)表達(dá)式自動(dòng)計(jì)算- 3 -流程圖說明：該流程圖分兩部分成，第一部分是中綴轉(zhuǎn)后綴部分，第二部分是用于后綴表達(dá)式求值的。（二）直接計(jì)算算法的流程圖輸入輸入表達(dá)式判斷數(shù)組轉(zhuǎn)化成浮點(diǎn)型數(shù) 操作符操作數(shù)棧 計(jì)算結(jié)果優(yōu)先級(jí)大于棧頂操作符進(jìn)棧輸出是優(yōu)先級(jí)大于 棧頂或?？辗癯鰲?1個(gè))2個(gè)數(shù)圖 2 接計(jì)算算法的流程圖流程圖說明：該流程圖進(jìn)過圖 1 改進(jìn)得到，只是缺少中綴轉(zhuǎn)后綴的部分。三、源代碼 三、源代碼下面給出的是