棧在表達式求值中的應用

李橙+丁國棟

摘要：棧是限定只能在表的一端進行插入和刪除的線性表。根據棧的這種存取特征，棧也被稱為后進先出表。生活中的穿衣脫衣、九連環游戲、括號匹配等都是應用棧的這一特點。棧的基本操作包括入棧、出棧、得到棧頂元素、判斷棧空、判斷棧滿等等。在該文中我們將討論棧在中綴表達式求值、后綴表達式求值以及后綴表達式轉換成中綴表達式中的應用。

關鍵詞：棧；數據結構；線性表；表達式求值

中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2014）34-8156-02

1 問題描述與分析

中綴表達式：運算符在兩個運算數之間的表達式，其中包含運算數、+、-、*、/等各種運算符以及括號。eg.3+9*（1-4）。按照“運算符的優先級”求值。

后綴表達式：運算符在兩個運算數之后的表達式，其中包含運算數、+、-、*、/等各種運算符但不包含括號，按照順序計算法求值。

[中綴表達式＼&后綴表達式＼&A+B*C＼&ABC*+＼&B*（D-C）+A＼&BDC-*A+＼&]

2 核心算法思想

2.1中綴表達式求值的算法思想

需要建立兩個輔助數據結構：數據棧用來存放要計算的數據以及產生的結果；符號棧用來存放運算符。

分析：先乘除，后加減，從左到右。

2.2 后綴表達式求值的算法思想

需要建立一個輔助數據結構：數據棧用來存放運算的數據以及產生的結果。

算法：自左向右掃描后綴表達式，直到遇到結束符為止。遇到運算數就進棧，遇到運算符就從數棧中退出兩個運算數，進行運算，將運算結果進棧，一直到所有運算全部執行完。

2.3 中綴表達式Mid[]轉換為后綴表達式Post[]

3 算法中涉及到的輔助數……