前綴表達式

前綴表達式

前綴表達式是一種沒有括弧的算術表達式,與中綴表達式不同的是,其將運算符寫在前面,運算元寫在後面。為紀念其發明者波蘭數學家Jan Lukasiewicz,前綴表達式也稱為“波蘭式”。例如,- 1 + 2 3,它等價於1-(2+3)。

基本釋義

前綴表達式就是前序表達式,是一種是由波蘭數學家揚·武卡謝維奇1920年引入的數學表達式方式。

例如,- 1 + 2 3,它等價於1-(2+3)。

注意事項

後綴表達式源自於前綴表達式,為了區分前綴和後綴表示,通常將後綴表示稱為逆波蘭表示;因前綴表示並不常用,所以有時也將後綴表示稱為波蘭表示。

運算優勢

前綴表達式是一種十分有用的表達式,將中綴表達式轉換為前綴表達式後,就可以只依靠出棧、入棧兩種簡單操作完全解決中綴表達式的全部運算。

例如,(a+b)*(c+d)轉換為*,+,a,b,+,c,d。

後面的前綴表達式的運算方式為:如果當前字元(或字元串)為數字或變數,則壓入棧內;如果是運算符,則將棧頂兩個元素彈出棧外並作相應運算,再將結果壓入棧內。當前綴表達式掃描結束時,棧里的就是中綴表達式運算的最終結果。對比中綴運算的步驟,不難發現前綴運算在計算機上的優勢。

求值方法

對前綴表達式求值,要從右至左掃描表達式,首先從右邊第一個字元開始判斷,若當前字元是數字則一直到數字串的末尾再記錄下來,若為運算符,則將右邊離得最近的兩個“數字串”作相應運算,然後以此作為一個新的“數字串”並記錄下來;掃描到表達式最左端時掃描結束,最後運算的值即為表達式的值。

例如:對前綴表達式“- 1 + 2 3”求值,掃描到3時,記錄下這個數字串,掃描到2時,記錄下這個數字串,當掃描到+時,將+右移做相鄰兩數字串的運算符,記為2+3,結果為5,記錄下5這個新數字串,然後繼續向左掃描,掃描到1時,記錄下這個數字串,掃描到-時,將-右移做相鄰兩數字串的運算符,記為1-5,結果為-4,此時關於這個表達式的全部運算已完成,故表達式的值為-4。

表達對照

中綴表達式轉化為前綴表達式的例子:

a+b ---> +,a,b

a+(b-c) ---> +,a,-,b,c

a+(b-c)*d ---> +,a,*,-,b,c,d

a+1+3 ---> +,+,a,1,3

轉換算法

(1) 首先構造一個運算符棧(也可放置括弧),運算符(以括弧為分界點)在棧內遵循越往棧頂優先權不降低的原則進行排列。

(2)從右至左掃描中綴表達式,從右邊第一個字元開始判斷:

如果當前字元是數字,則分析到數字串的結尾並將數字串直接輸出。

如果是運算符,則比較優先權。如果當前運算符的優先權大於等於棧頂運算符的優先權(當棧頂是括弧時,直接入棧),則將運算符直接入棧;否則將棧頂運算符出棧並輸出,直到當前運算符的優先權大於等於棧頂運算符的優先權(當棧頂是括弧時,直接入棧),再將當前運算符入棧。

如果是括弧,則根據括弧的方向進行處理。如果是右括弧,則直接入棧;否則,遇左括弧前將所有的運算符全部出棧並輸出,遇右括弧後將左右的兩括弧一起刪除。

(3) 重複上述操作(2)直至掃描結束,將棧內剩餘運算符全部出棧並輸出,再逆綴輸出字元串。中綴表達式也就轉換為前綴表達式了。

實例分析

將中綴表達式“1+((2+3)*4)-5”轉換為前綴表達式。

中綴表達式 前綴表達式 (棧頂)運算符棧(棧尾) 說明
5 5 5,是數字串直接輸出
- 5 - -,棧內無運算符,直接入棧
5 -) ),直接入棧
4 5 4 -) 4,是數字串直接輸出
* 5 4 -)* *,棧頂是括弧,直接入棧
) 5 4 - ) * ) ),直接入棧
3 5 4 3 - ) * ) 3,是數字串直接輸出
+ 5 4 3 - ) * ) + +,棧頂是括弧,直接入棧
2 5 4 3 2 - ) * )+ 2,是數字串直接輸出
( 5 4 3 2+ - ) * (,與棧里最後一個)抵消,並釋放它們之間的+
( 5 4 3 2+* - (,方法與上類同,請參考下一目錄
+ 5 4 3 2+* -+ +,優先權大於等於棧頂運算符,直接入棧
1 5 4 3 2+*1 -+ 1,是數字串直接輸出
5 4 3 2+*1+- 掃描結束,將棧內剩餘運算符全部出棧並輸出
- + 1 * + 2 3 4 5 逆綴輸出字元串

符號處理

對運算符的具體處理方法如下:

):直接入棧

(:遇)前,將運算符全部出棧並輸出;遇)後,將兩括弧一起刪除①

+、-:1

*、/、%:2

^:3

編程轉換

C++代碼

公式轉換

pascal代碼

相關詞條

熱門詞條

聯絡我們