數(shù)據(jù)結構課程設計---用兩種方式實現(xiàn)表達式自動計算

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

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

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

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

5、的方法將表達式依次掃描。只不過不同的是，當每取得的一個運算符的時候，都要與棧頂?shù)倪\算符進行比較，如果它的優(yōu)先級小于棧頂運算符優(yōu)先級時，取出棧頂運算符并從操作數(shù)棧中取棧頂兩個數(shù)進行運算，得到的結果則要存回操作數(shù)棧，就這樣邊掃描邊比較，再進行計算。遇到“） ”對運算符的處理相同。掃描結束后，把運算符棧的元素和操作數(shù)棧里的數(shù)進行運算。每次的運算結果再放入操作數(shù)棧，一直到計算到運算符棧空。最后操作數(shù)棧的棧頂留下的操作數(shù)即表達式的計算結果。以上就

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