6/7 演算法題詳解：Evaluate RPN Expressions 如何求逆波蘭表達式（RPN）的值

01-26

本視頻來自於北美CS刷題神器BitTiger Pro。

首先我們先來看一下什麼是RPN表達式。RPN全稱逆波蘭表示法（Reverse Polish Notation）。RPN也被稱為後綴表示法，RPN表達式不同於我們日常見到的表達式，它的所有操作符置於操作數的後面，故而逆波蘭記法不需要括弧來標識操作符的優先。當滿足以下兩個條件，我們就可以稱一個表達式為RPN表達式：

它是由單個數字或者帶有負號的數字序列，比如-23,123
它是以「A B OP」形式展現的，其中A，B是RPN表達式，OP是運算符+、-、*和/。

比方說「三加四」用RPN的方式就寫作「3 ,4 +」。我們可以很明顯地看到我們熟悉的加號被放到了後面，這就是RPN表達式顯著的特徵。

事實上RPN表達式可以被構造成一棵二叉樹，比方說RPN表達式「3,4,+,2,*,1,+」，它的樹結構就如下圖所示：

圖中，3和4構成了最小最底層的樹結構，然後乘以2構成了上一層的數，最後加上1形成了完整的二叉樹。

為了讓你更加了解RPN表達式，下面給出一些例子，大家動手試著把他們轉化為我們平時在使用的表達式。

在計算機科學編程者中，RPN表達式非常流行。當給出的是一般的計算表達式，經常轉化為RPN表達式來執行計算。原因顯而易見，從編程角度看，RPN表示式是一種更加簡單的格式。

讓我們開始講解如何實現RPN表示式的計算。還是舉例說明，比如「3,4,+,2,*,1,+」。我們從左到右開始計算這個表達式，首先我們讀取3和4，然後得到一個「+」，計算3加4的結果，是7，作為臨時結果，然後繼續讀取，2和「*」，就將臨時結果7乘以2，得到臨時結果14，最後讀取1和「+」，將14加1，得到最終結果15。

在這幾步計算中我們發現：

我們需要存儲臨時結果；
當我們讀取到運算符，就需要申請最近獲得的兩個數字（包括臨時結果和讀取的數字），臨時結果的插入和刪除執行「後入先出（last-in，first-out）」的原則。

從上述發現我們可以用堆（stack）可以很好的滿足RPN表達式的計算場景。

我們給出的解決方案就是從左到右掃描字元串，使用堆的思想實現，當我們讀取到操作數（operand），push到堆頂，當我們讀取到操作符（operator），從堆頂pull出最上面的2個數字，進行計算，然後把結果在push到堆頂。

讓我們來看一個例子：

讀取第一個字元，是1，它是一個數字，所以把它push到堆里。

讀取下一個字元，是2，它是一個數字，所以把它push到堆里。

讀取下一個字元，是3，它是一個數字，所以把它push到堆里。

讀取下一個字元，是4，它是一個數字，所以把它push到堆里。

讀取下一個字元，是「+」，它是一個運算符，按照我們的演算法，需要把堆頂的兩個元素拿出來進行計算，得到局部結果7。

把局部結果7 push到堆頂。

接下來到了第二個運算符，還是加號，需要把堆頂的兩個元素拿出來進行計算，得到局部結果9。

把局部結果9 push到堆頂。

接下來到了第三個運算符，還是加號，需要把堆頂的兩個元素拿出來進行計算，得到最終結果10。

實現代碼如下：

需要說明一下，在前文中我們提到需要使用堆來實現，但是在實際實現中，我們採用了Deque（雙端隊列，全名double-ended queue）來實現。事實上Deque是Java中一種普遍實現堆的方法。

回頭看一下代碼，首先中我們把傳入的表達式進行切割，然後是藉助分隔好的字元串數組進行循環，如果是數字，那就push到堆裡面，如果是運算符，按照運算符的類型分情況執行。等到數組訪問完，就返回最後一個堆裡面的元素。

最後我們分析一下性能。時間複雜度是O(n)，比較好理解，我們就是遍歷整個字元串。空間複雜度是O(n)，因為我們需要把每個原始數據和臨時結果存下來。

本視頻來自於北美CS刷題神器BitTiger Pro。

每月更新的BitTiger Pro是一個覆蓋了CS和數據科學方向最新高頻面試題的精講視頻庫。訂閱後，你可以在Code Evaluation System親自練習這道題。