關于線性表的一些總結——棧的應用之Infix、Prefix和Postfix互相轉換（前中字尾表達式轉換，noip初賽考試題目之一）

看着infix、prefix、postfix,感覺好進階，其實是三種算式表達式。

溫馨提示：本文較長，大家可以挑重點看

• 三種表達式的含義

在計算機中，對二進制算數表達式可以有三種不同的辨別方式：

字首表示法（簡稱字首式：Prefix）、中綴表示法（簡稱中綴式：Infix）、字尾表示法（簡稱字尾式：Postfix）。

給幾個例子讓大家感受一下差別，第一個例子很簡單明了啊。我實在不知道如何描述差別，給下定義：

例子	infix	prefix	postfix
1	a+b	+ab	ab+
2	(a+b)*c	*+abc	ab+c*
3	a*(b+c)	*a+bc	abc+*
4	a/b+c/d	+/ab/cd	ab/cd/+

1、字首式：字首表達式是一種沒有括号的算術表達式，其将運算符寫在前面，操作數寫在後面。為紀念其發明者波蘭數學家Jan Lukasiewicz，字首表達式也稱為“波蘭式”。例如，- 1 + 2 3，它等價于1-(2+3)。

2、中綴式：中綴表達式是一個通用的算術或邏輯公式表示方法。就是平時的運算式

3、字尾式：字尾表達式，又稱逆波蘭式，指的是不包含括号，運算符放在兩個運算對象的後面，所有的計算按運算符出現的順序，嚴格從左向右進行（不再考慮運算符的優先規則）。

我們計算機進行運算的時候，通常用的是字尾表達式！！！

因為計算機在讀入資料時，通常是從左向右掃描，如果采用我們平時用的中綴式會很麻煩，因為會多次掃描來确定運算優先級。字首式則需要兩次，字尾式卻隻需要一次。（究竟是怎麼樣的一次下面會詳細給代碼，最後一個點）

是以說字尾式大大縮短了讀入時間。

• 進行轉換（手動模拟）

運算符	優先級	結合性
（，）	高	左結合
（正号）+、負号-	↑	左結合
（幂次方）^、↑	I	右結合
×、÷	I	左結合
+、-	I	左結合
（關系）<、>、≤、≥	I	左結合
（邏輯）Not、~	I	左結合
（邏輯）And	I	左結合
（邏輯）or	↓	左結合
=	低	右結合

上面是關于二進制算術中符号的優先級排序，我們按優先級來對式子進行計算，同樣按照優先級對于式子進行轉換。

特殊的左結合要強制記住。

舉兩個栗子，大家按照這個方法進行類比推廣到全部的轉換。

講兩個最常用的，使用括号法（按照運算符優先級和結合性）：

• infix→postfix的步驟：

  1、對于中綴式，先加上完整的括号配對。完整是像這樣（（a+b）+c）

  平時最外面是不加的但現在都加上。

  2、将運算符取代最近的右括号。（按優先級來）

  像這樣 ：

  (1)first step:(（ab++c)

  (2)second step:（（ab+c+

  3、删除左括号

  像這樣

  （1）first step:(ab++c)

  (2)second step:ab+c+

• infix→prefix的步驟：

  1、對于中序式，先加上完整的括号配對

  2、将運算符取代最近的左括号

  3、删除右括号，予以輸出即可

這裡最好自己轉化一下，手動搞一下。畢竟初賽是要靠填空的。這一塊多練就好，自己練多了看一下就會轉了。

• 棧的方法轉化infix→postfix的算法（逆波蘭式）

儲存運算符的結構應該是個棧，從棧底到棧頂的運算符的優先級是從低到高的，是以運算後輸出應該是棧頂到棧底。 （就是反向輸出）

以下是算法思想：

1）設立運算符棧。

2）設表達式的結束符為“#”，預設運算符的棧底為“#”。

3）若目前字元是操作數，則直接發送給字尾式。

4）若目前字元為運算符且優先數大于棧頂運算符，則進棧，否則退出棧頂運算符發給字尾式。

5）若目前字元是結束符，則自棧頂至棧底依次講棧中所有運算符發給字尾式。

6）“（”對它之前後的運算符起隔離作用，則若目前運算符為“（”時進棧。

7）“）”可視為自應當左括弧開始的表達式的結束符，則從棧頂起，依次退出棧頂運算符發給字尾式直至棧頂字元為“（”止。

（用詞好正經官方哈哈哈）

其實思想是很好想的，隻要手動推過逆波蘭式就好很多了。

附上模闆測評題：

題目描述

所謂字尾表達式是指這樣的一個表達式：式中不再引用括号，運算符号放在兩個運算對象之後，所有計算按運算符号出現的順序，嚴格地由左而右新進行（不用考慮運算符的優先級）。

如：3*(5–2)+7對應的字尾表達式為：3．5．2．-*7．[email protected]。’@’為表達式的結束符号。‘.’為操作數的結束符号。

輸入輸出格式

輸入格式：

輸入：字尾表達式

輸出格式：

輸出：表達式的值

輸入輸出樣例

輸入樣例#1：

3.5.2.-*[email protected]

輸出樣例#1：

16

說明

字元串長度，1000内。

傳送門：https://www.luogu.org/problemnew/show/P1449

大家自己去看題解吧！！！加油！！