郭曉穎 陳勇濤 葉中華 陶慧杰 河北農(nóng)業(yè)大學(xué)信息科學(xué)與技術(shù)學(xué)院

基于堆棧的四則運算總結(jié)及優(yōu)化

郭曉穎 陳勇濤 葉中華 陶慧杰 河北農(nóng)業(yè)大學(xué)信息科學(xué)與技術(shù)學(xué)院

本文用c語言對算數(shù)表達(dá)式進(jìn)行分析與設(shè)計，該算法可以實現(xiàn)整數(shù)，浮點數(shù)，帶括號的加、減、乘、除四則運算。四則表達(dá)式的算法實現(xiàn)是堆棧的典型應(yīng)用，在此基礎(chǔ)上，首先介紹分析后綴的計算，進(jìn)而然后介紹中綴的兩類算法，基于優(yōu)先級表的后綴轉(zhuǎn)中綴算法、基于優(yōu)先級表的邊掃描邊計算法以及優(yōu)化過后的加二法。

算數(shù)表達(dá)式 算法 棧 括號

算數(shù)表達(dá)式由操作數(shù)，運算符和分界符構(gòu)成，可以用中綴和后綴表達(dá)式來表示。中綴中的運算符位于兩個操作數(shù)之間，后綴的運算符位于操作數(shù)之后。中綴與后綴表達(dá)式的操作數(shù)的先后次序完全一樣，但運算符的先后次序不一致，后綴中沒有括號，后綴的運算順序就是其執(zhí)行順序。

1 后綴表達(dá)式的實現(xiàn)算法

算法流程：

（1）建立數(shù)據(jù)棧

（2）掃描后綴表達(dá)式，判斷掃描到的符號，如果后綴表達(dá)式遍歷完畢，轉(zhuǎn)到5）

（3）如果符號為操作數(shù)，進(jìn)棧

（4）如果符號是運算符，判斷棧是否為空，為空，轉(zhuǎn)到5），否則取出數(shù)據(jù)棧棧頂元素，進(jìn)行計算，運算結(jié)構(gòu)入棧。轉(zhuǎn)到2）

（5）算法結(jié)束

2 中綴表達(dá)式的實現(xiàn)算法

2.1 利用中綴轉(zhuǎn)后綴的算法實現(xiàn)

算法流程：

（1）建立符號棧

（2）掃描中序表達(dá)式 ，判斷掃描到的符號

I:如果掃描到的是操作數(shù)， 直接輸出

II:如果掃描到的是運算符，判斷運算符

i : ‘(‘ 直接入棧

ii : ‘)’ 將符號棧中的元素依次出棧并輸出 , 直到 ‘(‘, ‘(‘只出棧, 不輸出

iii: 如果是其他的運算符, 將符號棧中的元素依次出棧并輸出,直到遇到’(‘或者比當(dāng)前符號優(yōu)先級更低的符號， 將這個操作符入棧。

（3）掃描完后, 將棧中剩余符號依次輸出

2.2 利用優(yōu)先級表實現(xiàn)

算法實現(xiàn)：

直接用中綴表達(dá)式求解需要兩個棧，一個是用于存放操作數(shù)的“數(shù)字”棧，一個是用于存放運算符的“符號”棧。從左到右掃描表達(dá)式

I:如果遇到的是數(shù)字直接進(jìn)數(shù)字棧

II:如果掃描到的是運算符,拿此運算符和符號棧頂?shù)倪\算符進(jìn)行比較

i:若這個符號的優(yōu)先級大，則把這個符號進(jìn)符號棧，繼續(xù)掃描

ii:若小于從數(shù)字棧中連續(xù)出棧兩個操作數(shù)，在從符號棧出棧一個符號，在把剛從符號棧出棧的運算符和剛從數(shù)字棧出棧的兩個操作數(shù)進(jìn)行運算，將運算結(jié)果放到數(shù)字棧，然后，在把掃面到的運算符和棧頂比較。

iii:若相等則從符號棧出棧一個，繼續(xù)掃描

III:當(dāng)掃描到表達(dá)式結(jié)尾時，若符號棧不空，則從數(shù)字棧中出棧兩個，從符號棧出棧一個，將運算結(jié)果放到數(shù)字棧，知道符號棧為空，此時數(shù)字棧的棧頂就是表達(dá)式的值

2.3 優(yōu)化加二法

算法流程：

（1）遍歷中綴表達(dá)式，初始化+，-優(yōu)先級為1，乘除優(yōu)先級為2，（優(yōu)先級變量為temp即當(dāng)前優(yōu)先級加2，）為temp當(dāng)前優(yōu)先級減2

（2）掃描到的當(dāng)前符號為運算符

I:當(dāng)前運算符的優(yōu)先級為當(dāng)前優(yōu)先級變量temp=temp+grade

II：如果是第一個運算符，將當(dāng)前運算符和優(yōu)先級無條件入棧，轉(zhuǎn)到4）

III:否則，取出當(dāng)前棧頂?shù)倪\算符及其優(yōu)先級，判斷當(dāng)前掃描到的運算符和棧頂運算符的優(yōu)先級

IV:若當(dāng)前掃描到的運算符優(yōu)先級高，將當(dāng)前運算符及其優(yōu)先級入棧，轉(zhuǎn)到4）

V:若取出的棧頂運算符的優(yōu)先級高，接連取出數(shù)據(jù)棧的棧頂元素及其符號棧的棧頂元素，進(jìn)行運算，結(jié)果保存到數(shù)據(jù)棧。計算完畢，取出符號棧的棧頂元素，如果是’#’，循環(huán)結(jié)束,否則轉(zhuǎn)到V，繼續(xù)循環(huán)。

VI：將掃描到的元素及其優(yōu)先級入棧

（3）掃描到的當(dāng)前符號為操作數(shù)，將操作數(shù)入棧

（4）掃描下一個符號，轉(zhuǎn)到1），若掃描完畢，轉(zhuǎn)到5)

（5）中綴表達(dá)式遍歷完畢

i:將數(shù)據(jù)棧棧頂元素依次出棧(兩次),將符號棧棧頂元素出棧，計算結(jié)果壓入數(shù)據(jù)棧，取出當(dāng)前符號棧棧頂元素，若是’#’，循環(huán)結(jié)束，轉(zhuǎn)到ii）否則，轉(zhuǎn)到i）繼續(xù)執(zhí)行

ii）取出數(shù)據(jù)棧棧頂元素即為所求

該算法巧妙之處在于，對于括號的處理，加二法省去了優(yōu)先級表的構(gòu)造，僅僅利用一個變量temp加減2判定出了優(yōu)先級，遇’(’temp加2，遇’)’temp減2，實現(xiàn)了在’(‘括號中的運算符比括號外的運算符高，遇到’)’，temp減2，運算符恢復(fù)原優(yōu)先級。

3 總結(jié)

本文主要對優(yōu)化的加二法進(jìn)行闡述，體現(xiàn)出算法在設(shè)計時的精巧，三類算法的時間復(fù)雜度都是O(N)，不過在大部分計算器應(yīng)用中，采用后綴表達(dá)式的算法，該算法省去了優(yōu)先級的判斷，將算法時間集中在了運算上，更加符合計算器特點。在日常計算中，人們往往喜歡帶上括號運算，便于理解與交互，中綴表達(dá)式的優(yōu)化運算也是很重要。

[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，1997

[2]周桂紅.數(shù)據(jù)結(jié)構(gòu) 1版[M].北京：北京郵電大學(xué)出版社，2010