基于堆棧的四則運算總結及優化

郭曉穎 陳勇濤 葉中華 陶慧杰 河北農業大學信息科學與技術學院

基于堆棧的四則運算總結及優化

郭曉穎 陳勇濤 葉中華 陶慧杰 河北農業大學信息科學與技術學院

本文用c語言對算數表達式進行分析與設計，該算法可以實現整數，浮點數，帶括號的加、減、乘、除四則運算。四則表達式的算法實現是堆棧的典型應用，在此基礎上，首先介紹分析后綴的計算，進而然后介紹中綴的兩類算法，基于優先級表的后綴轉中綴算法、基于優先級表的邊掃描邊計算法以及優化過后的加二法。

算數表達式 算法 棧 括號

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

1 后綴表達式的實現算法

算法流程：

（1）建立數據棧

（2）掃描后綴表達式，判斷掃描到的符號，如果后綴表達式遍歷完畢，轉到5）

（3）如果符號為操作數，進棧

（4）如果符號是運算符，判斷棧是否為空，為空，轉到5），否則取出數據棧棧頂元素，進行計算，運算結構入棧。轉到2）

（5）算法結束

2 中綴表達式的實現算法

2.1 利用中綴轉后綴的算法實現

算法流程：

（1）建立符號棧

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

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

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

i : ‘(‘ 直接入棧

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

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

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

2.2 利用優先級表實現

算法實現：

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

I:如果遇到的是數字直接進數字棧

II:如果掃描到的是運算符,拿此運算符和符號棧頂的運算符進行比較

i:若這個符號的優先級大，則把這個符號進符號棧，繼續掃描

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

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

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

2.3 優化加二法

算法流程：

（1）遍歷中綴表達式，初始化+，-優先級為1，乘除優先級為2，（優先級變量為temp即當前優先級加2，）為temp當前優先級減2

（2）掃描到的當前符號為運算符

I:當前運算符的優先級為當前優先級變量temp=temp+grade

II：如果是第一個運算符，將當前運算符和優先級無條件入棧，轉到4）

III:否則，取出當前棧頂的運算符及其優先級，判斷當前掃描到的運算符和棧頂運算符的優先級

IV:若當前掃描到的運算符優先級高，將當前運算符及其優先級入棧，轉到4）

V:若取出的棧頂運算符的優先級高，接連取出數據棧的棧頂元素及其符號棧的棧頂元素，進行運算，結果保存到數據棧。計算完畢，取出符號棧的棧頂元素，如果是’#’，循環結束,否則轉到V，繼續循環。

VI：將掃描到的元素及其優先級入棧

（3）掃描到的當前符號為操作數，將操作數入棧

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

（5）中綴表達式遍歷完畢

i:將數據棧棧頂元素依次出棧(兩次),將符號棧棧頂元素出棧，計算結果壓入數據棧，取出當前符號棧棧頂元素，若是’#’，循環結束，轉到ii）否則，轉到i）繼續執行

ii）取出數據棧棧頂元素即為所求

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

3 總結

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

[1]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，1997

[2]周桂紅.數據結構 1版[M].北京：北京郵電大學出版社，2010