字首、中綴、字尾表達式

字首、中綴、字尾表達式是對表達式的不同記法，其差別在于運算符相對于操作數的位置不同，字首表達式的運算符位于操作數之前，中綴和字尾同理

舉例：

中綴表達式：1 + (2 + 3) × 4 - 5

字首表達式：- + 1 × + 2 3 4 5

字尾表達式：1 2 3 + 4 × + 5 -

中綴表達式

中綴表達式是一種通用的算術或邏輯公式表示方法，操作符以中綴形式處于操作數的中間。中綴表達式是人們常用的算術表示方法。

雖然人的大腦很容易了解與分析中綴表達式，但對計算機來說中綴表達式卻是很複雜的，是以計算表達式的值時，通常需要先将中綴表達式轉換為字首或字尾表達式，然後再進行求值。對計算機來說，計算字首或字尾表達式的值非常簡單。

字首表達式

字首表達式的運算符位于兩個相應操作數之前，字首表達式又被稱為字首記法或波蘭式

字首表達式的計算機求值

1. 從右至左掃描表達式
2. 遇到數字時，将數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（棧頂元素 op 次頂元素），并将結果入棧
3. 重複上述過程直到表達式最左端，最後運算得出的值即為表達式的結果

示例：

計算字首表達式的值：- + 1 × + 2 3 4 5

1. 從右至左掃描，将5，4，3，2壓入堆棧；

   2）遇到+運算符，彈出2和3（2為棧頂元素，3為次頂元素），計算2+3的值，得到5，将5壓入棧；

   3）遇到×運算符，彈出5和4，計算5×4的值，得到20，将20壓入棧；

   4）遇到1，将1壓入棧；

   5）遇到+運算符，彈出1和20，計算1+20的值，得到21，将21壓入棧；

   6）遇到-運算符，彈出21和5，計算21-5的值，得到16為最終結果

可以看到，用計算機計算字首表達式是非常容易的，不像計算字尾表達式需要使用正則比對

字尾表達式

字尾表達式與字首表達式類似，隻是運算符位于兩個相應操作數之後，字尾表達式也被稱為字尾記法或逆波蘭式

字尾表達式的計算機求值

與字首表達式類似，隻是順序是從左至右：

1. 從左至右掃描表達式
2. 遇到數字時，将數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（次頂元素op 棧頂元素 ），并将結果入棧
3. 重複上述過程直到表達式最右端，最後運算得出的值即為表達式的結果

計算

計算字尾表達式的值：1 2 3 + 4 × + 5 -

1）從左至右掃描，将1，2，3壓入棧；

2）遇到+運算符，3和2彈出，計算2+3的值，得到5，将5壓入棧；

3）遇到4，将4壓入棧

4）遇到×運算符，彈出4和5，計算5×4的值，得到20，将20壓入棧；

5）遇到+運算符，彈出20和1，計算1+20的值，得到21，将21壓入棧；

6）遇到5，将5壓入棧；

7）遇到-運算符，彈出5和21，計算21-5的值，得到16為最終結果

中綴表達式轉化為字首和字尾表達式

轉化步驟：

1. 按照運算符的優先級對所有的運算機關加括号
2. 将運算符移動到對應括号的前面（字首表達式）或後面（字尾表達式）
3. 去掉括号，得到字首或字尾表達式

中綴表達式：1+(2+3)×4-5

1）加括号

式子變成 ((1+((2+3)×4))-5)

2）移動運算符

小結

• • 字首、中綴、字尾是根據運算符與操作數的相對位置來劃分的
  • 中綴表達式符合人的計算習慣，而字首和字尾表達式适合計算機計算
  • 字首表達式和字尾表達式計算的時候都是從一個方向掃描表達式，遇到數字壓入棧，遇到運算符彈出棧頂的兩個數進行運算并将結果入棧，重複知道結束
  • 字首和字尾表達式已經内在地包含運算順序，是以不用括号來确定優先級