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

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

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

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

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

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

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

算法流程：

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

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

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

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

（5）算法結(jié)束

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

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

算法流程：

（1）建立符號棧

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

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

II:如果掃描到的是運(yùn)算符，判斷運(yùn)算符

i : ‘(‘ 直接入棧

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

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

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

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

算法實(shí)現(xiàn)：

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

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

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

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

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

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

III:當(dāng)掃描到表達(dá)式結(jié)尾時(shí)，若符號棧不空，則從數(shù)字棧中出棧兩個(gè)，從符號棧出棧一個(gè)，將運(yùn)算結(jié)果放到數(shù)字棧，知道符號棧為空，此時(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)前符號為運(yùn)算符

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

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

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

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

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

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

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

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

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

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

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

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

3 總結(jié)

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

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

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