數據結構之棧在表達式求值及轉換中的應用

• 1 棧及表達式的基本定義
• 2 棧在表達式求值過程以及轉換中的應用

1 棧及表達式的基本定義

1.1棧的定義

棧(stack)是限定僅在表尾進行插入或刪除操作的線性表。因此，對棧來說，
表尾端有其特殊含義，稱為棧頂(top)，相應地，表頭端稱為棧底(bottom)。不含元素的空表稱為空棧。棧也稱為后進先出表。下面將給出關于棧基本操作的相關函數：
InitStack(&S):構造一個空棧S
GetTop(S,&e):用e返回S的棧頂元素。
Push(&S,e):插人元素e為新的棧頂元素。
Pop(&s,&e):刪除S的棧頂元素，并用e返回其值。
Precede(m,n):運算符的優先級比較函數。

1.2表達式的定義

任何一個表達式都是由操作數(operand)、運算符(operator)和界限符(elimite)組成的，我們稱它們為單詞。一般地，操作數既可以是常數也可以是被說明為變量或常量的標識符；運算符可以分為算術運算符、關系運算符和邏輯運算符3類；基本界限符有左右括號和表達式結束符等。

1.3表達式的分類

表達式一般分為前綴表達式，中綴表達式和后綴表達式，在計算機中，計算后綴表達式值的時間空間消耗往往比計算中綴表達式的消耗少，因此我們通常將普通表達式轉化為某種類型表達式來達到減少復雜度的目的。
1.3.1 前綴表達式 前綴表達式是將運算符寫在前面，操作數寫在后面。為紀念其發明者波蘭數學家Jan Lukasiewicz，前綴表達式也稱為“波蘭式”。
1.3.2 中綴表達式 中綴表達式是指運算符在兩個操作數的中間。即平時常用的表達式脫括號后的形式。
1.3.3.后綴表達式 后綴表達式是將運算符放在兩個運算對象的后面，計算時按運算符出現的順序，嚴格從左向右進行(不再考慮運算符的優先規則)。運用次數最多，又稱“逆波蘭式”。
對于算術表達式Exp=ab+(c-d/e)f，它的三種表達形式為：前綴式:+ab-c/def，中綴式:ab+c-d/ef，后綴式:abcde/-f+。

1.4關于上述表達式的相關結論

1.操作數之間的相對次序不變；
2.運算符的相對次序不同；
3.中綴式丟失了括弧信息，致使運算的次序不確定；
4.前綴式的運算規則為：連續出現的兩個操作數和在它們之前且緊靠它們的運算符構成一個最小表達式；
5.后綴式的運算規則為：運算符在式中出現的順序恰為表達式的運算順序；每個運算符和在它之前出現且緊靠它的兩個操作數構成一個最小表達式。

2 棧在表達式求值過程以及轉換中的應用

2.1 表達式求值算法的基本思路

為了敘述的簡潔，我們僅討論簡單算術表達式的求值問題。這種表達式只含加、減、乘、除4種運算符。讀者不難將它推廣到更一般的表達式上。
2.1.1 求值算法中的主要數據結構 我們分別用順序棧來寄存表達式的操作數和運算符。為了實現算符優先算法，可以使用兩個工作棧。一個稱做OPTR，用以寄存運算符；另一個稱做OPND，用以寄存操作數或運算結果。
2.1.2 關于表達式的分析與判斷 表達式求值程序的關鍵是對數字與運算符的判斷和運算符優先級的判斷，以及出棧的運算。可以建立兩個棧，分別存儲數字與運算符，棧OPTR存運算符，棧OPND存數字。依次讀取表達式的字符串。讀取字符的時候需要判斷字符的類型，先判斷是數字還是運算符：
第一步，如果是數字，把數字壓入棧OPND。
第二步，如果是運算符，那么在壓入運算符之前，先將要壓入的與棧頂的運算符優先級相比較，此時有三種情況：
1.如果當前的運算符優先級等于棧頂，則脫括號并接受下一字符；
2.若當前的運算符優先級大于棧頂的，則壓入；
3.若當前的運算符優先級小于棧內時，彈出棧頂的運算符，同時彈出兩組數字，經過運算符的運算后再重新壓到棧內。
為了方便判斷運算結束，在存儲運算符之前先將“#”壓入棧OPTR中，在輸入表達式時以“#”結束，所以當接受的運算符為‘#’并且OPTR棧頂的元素也為‘#’來作為運算結束的條件，經過上述的討論，最后棧OPND的數值，即為表達式求值的最終結果。
2.1.3 表達式求值例題分析
例1：利用上述算法對算數表達式3*（7-2）求值
下圖中，左側為OPTR棧，右側為OPND棧。
步驟1：“＃”入OPTR棧

圖1

步驟2：“3”入OPND棧

圖2

步驟3：“”比此時的OPTR棧的頂元素“#”的優先權高，“”入OPTR棧

步驟4.：“（”比此時的OPTR棧頂元素“*”的優先權高，“（”入OPTR棧

步驟5：“7”是數字，進OPND棧

步驟6.：“-”比此時的OPTR棧頂元素“（”的優先權高，“-”入OPTR棧

步驟7.：“2”入OPND棧

圖7

步驟8.：“）”比此時的OPTR棧頂元素“-”的優先權低，執行Pop(OPTR,theta);操作，“-”退OPTR棧，OPND棧中退出兩個數，在該步操作中執行“7-2”，把得到的結果5壓入OPND棧中，此時兩個棧的元素為下圖：

圖8

步驟9：“）”繼續和OPTR棧此時的棧頂元素“（”相比，發現相等，則脫括號，并接受下一字符，此時的OPND棧為：

圖9

步驟10：我們通常以“#”來作為表達式的末尾，所以最后需要判斷優先級大小的是“#”和OPTR的棧頂元素“”，此時發現棧頂元素“”的優先級高，則棧頂元素“”出棧，OPND棧中出兩個元素，執行“35”操作，得到15，壓入OPND棧內，最后兩個“#”相等，while循環結束。則OPND棧中的元素就是該表達式的最終求值。此時，兩個棧的元素為：

圖10

最后結果為3*（7-2）=15。
2.1.4 算法時間和空間性能分析
1.時間復雜度：對于含n個字符的表達式，無論是對其進行合法性檢測還是對其進行入棧出棧操作n次，因此其時間復雜度為0(n)。
2.空間復雜度：由于在本程序中，在為算符棧(OPTR)和操作數棧(0PND)涉及到兩種情況時申請空間，一方面分別為OPTR棧和0PND棧申請了初始的存儲單元，均為STACKINITSIZE=100個；另一方面，考慮到兩個棧在處理具體的算術表達式時，有可能會出現溢出的情況，即棧的初始的存儲空間不夠用，這時需要為其申請額外的存儲空間，每溢出一次，就為其申請存儲單元STACKINCREMENT=10個，所以，本程序的算法的空間復雜度一方面取決于算術表達式的長度，另一方面取決于本程序的所有代碼所占用的存儲空間大小。

2.2 后綴表達式求值算法
2.2.1求值算法中的主要數據結構 根本思想就是先找運算符，再找操作數，因為操作數來的早晚與運算順序無關，所以，我們可以設置一個棧來存儲操作數，只要是操作數據進棧，只要是運算符就從棧中取出兩個操作數，經過運算符的運算后再重新壓到棧內，最后棧頂的值就是我們要求的最后結果。

2.2.2基于C語言的算法
下面給出其基本算法：
int GetValue NiBoLan(char *str)/對逆波蘭式求值
{ p=str;InitStack(s); //s為操作數棧
while(*p!="#’)
{ if(Isdigit(*p)) push(s,*p);
else {
pop(s,a);pop(s,b);
r=compute(b,*p,a); //假設compute為執行雙目運算的過程
push(s,r);}//else
}//while
}//GetValue_ NiBoLan

2.3 原表達式求后綴表達式算法

2.3.1 原表達式求后綴式算法思想 因為運算符來的早晚與運算順序無關，首先設立暫存運算符的棧，設表達式的結束符號為“#”，預設運算符棧的棧底為“#”，若當前字符是操作數，則直接發送給后綴式；若當前運算符的優先數高于棧頂運算符，則進棧；否則，退出棧頂運算行發送給后綴式；“(”對它之前后的運算符起隔離作用，“)”可視為自相應左括弧開始的表達式的結束符。
2.3.2 原表達式求后綴式例題分析
對原表達式2*（9+6/3-5）+4求其后綴式：

最后求得后綴表達式為：2963/+5-*4+。

參考文獻：
[1] 嚴蔚敏，吳偉民.數據結構C語言版[M].北京:清華大學出版社。

這是自己總結的表達式求值的基本算法，也是自己的寫的一篇很簡單的課程論文，主要是給出了相應的例題分析，圖片是自己做的，不是很美觀，有錯誤歡迎大家評論區指出討論，大家一起進步！

總結

以上是生活随笔為你收集整理的数据结构-栈--表达式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。