深入剖析字首、中綴、字尾表示式以及表示式求值

前言

在本篇文章當中主要跟大家介紹以下幾點

字首、中綴和字尾表示式。
如何將中綴表示式轉化成字尾表示式。
如何使用字尾表示式進行求值。

表示式求值這是一個比較經典的計算機系統基礎問題，但是整個過程比較抽象，本文主要通過圖解的方法幫助大家理解這個問題。

表示式介紹

字尾表示式也稱作逆波蘭表示式，字首表示式也稱作波蘭表示式，這個是因為這是由波蘭數學家楊-武卡謝維奇提出來的，用於簡化命題邏輯的一種方法。

中綴表示式

我們常見的數學表示式就是中綴表示式，比如說：\(1 + 2\)，像這種我們從小到大經常見到的表示式就叫做中綴表示式，這個表示式的特點就是將運運算元（加減乘除）放在兩個運算元（數位）中間。

字尾表示式

字尾表示式和中綴表示式的最大區別就是，他不是將運運算元放在運算元中間，而是將運運算元放在運算元後面，比如上面的中綴表示式\(1 + 2\)轉化成字尾表示式就為\(12+\)。

字首表示式

字首表示式就是將運運算元放在運算元的前面，比如上面的中綴表示式\(1 + 2\)轉化成字首表示式之後為\(+12\)。

表示式之間轉化的例子

上面的表示式還是比較簡單，可能不足以幫助大家好好理解表示式之間的轉化過程。

中綴表示式：\(A + B * (C - D) - E / F\)

現在我們來將上面的中綴表示式轉化成字尾表示式，我們的第一個計算的部分如下（括號裡面的優先計算）：

根據我們的轉化原理：將運運算元放在運算元後面，

上面的得到的字尾表示式繼續進行轉化（現在需要計算\(B\)乘以後面的那個部分）：

繼續進行轉化（從左往後進行計算）：

繼續進行轉化（除法的優先順序比減法高）：

得到最終的結果：

程式如何將中綴表示式轉化成字尾表示式

將中綴表示式轉化成字尾表示式有以下幾條規則（下面的棧是儲存操作符的棧，而且只儲存操作符）：

從左到右進行遍歷。
遇到運算元，直接加入到字尾表示式當中。
遇到界限符。遇到「(」直接入棧，遇到「)」則依次彈出棧內運運算元並加入字尾表示式，直到彈出「(」為止，注意:「(」不加入字尾表示式。
遇到運運算元。依次彈出棧中優先順序高於或等於當前運運算元的所有運運算元，並加入字尾表示式，若碰到「(」或棧空則停止。之後再把當前運運算元入棧。

現在我們根據上面的規則來將上文當中的中綴表示式轉化成字尾表示式。

遍歷到\(A\)，根據第二條規則，將\(A\)加入到字尾表示式當中，當前的字尾表示式為：\(A\)。

現在遍歷到加號，根據前面的規則需要彈出棧裡面優先順序大的運運算元，再將加號加入到棧中，當前的字尾表示式為\(A\)。

遍歷到\(B\)，直接加入到字尾表示式當中，目前的字尾表示式為\(AB\)。

遍歷到\(*\)，根據規則直接將其加入到棧中，當前字尾表示式為\(AB\)。

遍歷到\((\)，根據規則直接將其加入到棧中，當前字尾表示式為\(AB\)。

遍歷到\(C\)，則直接將其加入到字尾表示式當中，當前字尾表示式為\(ABC\)。
遍歷到\(-\)，根據規則將其加入到棧中，當前字尾表示式為\(ABC\)。

遍歷到\(D\)，則將其直接加入到字尾表示式當中，當前的字尾表示式為\(ABCD\)。
遍歷到\()\)，則需要將棧中的符號彈出，直到遇到\((\)，當前的字尾表示式為\(ABCD-\)。

遍歷到\(-\)，需要將棧中優先順序大於等於\(-\)的運運算元彈出，則當前的字尾表示式為\(ABCD-*+\)，再將\(-\)壓入棧中。

遍歷到\(E\)，直接將數位加入到字尾表示式當中，則當前的字尾表示式為\(ABCD-*+E\)。
遍歷到\(/\)，將棧中優先順序大於等於\(/\)的運運算元，再將\(/\)壓入到棧中，當前的字尾表示式為\(ABCD-*+E\)。

遍歷到\(F\)，直接將其加入到字尾表示式當中，則當前的字尾表示式為\(ABCD-*+EF\)。
最終將棧中所有的運運算元都彈出，得到的字尾表示式為\(ABCD-*+EF/-\)。

經過上面的過程就可以將一箇中綴表示式轉成字尾表示式了，大家如果想要程式碼實現，只需要在遍歷資料的時候根據上面四個規則一個個進行判斷即可，程式並不困難，就是邏輯稍微有點多，需要考慮更多的問題，在寫程式碼的時候需要細緻一點。

字尾表示式求值

在前文當中我們已經得到了表示式\(A + B * (C - D) - E / F\)的字尾表示式為\(ABCD-*+EF/-\)。現在我們需要將這個字尾表示式進行求值。根據字尾表示式求值主要有以下兩條規則：

如果遇到數位直接將其加入到數位棧。
如果遇到操作符直接從運算元棧彈出兩個資料進行對應的運算，再將運算結果加入到棧中。

現在我們進行字尾表示式的求值過程;

首先前面四個\(ABCD\)都是數位，根據上面提到的第一條規則，我們都需要將數位壓入到棧當中，因此遍歷四個數位之後，情況如下：

現在遍歷到\(-\)，我們需要將\(D\)和\(C\)彈出，然後進行\(-\)操作的運算，再將結果壓入棧中。

現在遍歷到\(*\)，我們需要將\(C-D=M\)和\(B\)彈出，進行乘法運算，然後將結果壓入棧中。

現在我們遍歷到\(+\)，需要將棧中剩餘的兩個數彈出，進行加法運算，在將結果壓棧。

遍歷\(EF\)都需要將這兩個數壓入到棧當中。

現在遍歷到\(/\)，需要進行除法運算，在將得到的結果壓入到棧中。

最後遍歷到\(-\)，將棧中的兩個數彈出棧，進行減法運算得到最後的結果。

相信經過上面過程你對字尾表示式求值的過程已經非常清楚了。

程式碼實現

在LeetCode中有一道題就是根據字尾表示式求值——劍指 Offer II 036. 字尾表示式

根據逆波蘭表示法，求該字尾表示式的計算結果。

有效的算符包括 +、-、*、/ 。每個運算物件可以是整數，也可以是另一個逆波蘭表示式。

說明：

整數除法只保留整數部分。

給定逆波蘭表示式總是有效的。換句話說，表示式總會得出有效數值且不存在除數為 0 的情況。

範例 1：

輸入：tokens = ["2","1","+","3","*"]
輸出：9
解釋：該算式轉化為常見的中綴算術表示式為：((2 + 1) * 3) = 9

範例 2：

輸入：tokens = ["4","13","5","/","+"]
輸出：6
解釋：該算式轉化為常見的中綴算術表示式為：(4 + (13 / 5)) = 6

上面問題的程式碼如下：

class Solution {
  public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    for (String token : tokens) {
      switch (token) {
        case "+": {
          int a = stack.pop();
          int b = stack.pop();
          stack.push(b + a);
          break;
        }
        case "-": {
          int a = stack.pop();
          int b = stack.pop();
          stack.push(b - a);
          break;
        }
        case "*": {
          int a = stack.pop();
          int b = stack.pop();
          stack.push(b * a);
          break;
        }
        case "/": {
          int a = stack.pop();
          int b = stack.pop();
          stack.push(b / a);
          break;
        }
        default:
          stack.push(Integer.parseInt(token));
          break;
      }
    }
    return stack.pop();
  }
}

總結

本文主要給大家介紹瞭如何將中綴表示式轉化成字尾表示式，以及程式碼根據字尾表示式求值。本文所談到的問題可能相對於其他問題來說邏輯上可能更加複雜，需要大家自己閱讀和根據文字和圖進行理解。

以上就是本文所有的內容了，希望大家有所收穫，我是LeHung，我們下期再見！！！（記得點贊收藏哦！）

更多精彩內容合集可存取專案：https://github.com/Chang-LeHung/CSCore

關注公眾號：一無是處的研究僧，瞭解更多計算機（Java、Python、計算機系統基礎、演演算法與資料結構）知識。

22張圖帶你深入剖析字首、中綴、字尾表示式以及表示式求值