RPN(逆波蘭表達式)

介紹

逆波蘭表達式(Reverse Polish Notation)，簡稱為RPN，由J. Lukasiewicz（12/21/1878 – 02/13/1956）發展而來，在避免使用括弧的情況下，完成表達式的有優先權的運算。RPN表達式由運算元（operand）和運算符（operator）構成，不使用括弧，即可表示帶優先權的運算關係，但是須使用元字元，如空格。一般在計算機中，使用棧操作進行RPN表達式的計算。遇到運算元就入棧，遇到運算符，就對當前棧頂元素進行相應的一元或者二元運算。

實例

例子：

普通表達式：0!+123+4*(5*6!+7!/8)/9

RPN表達式：0 ! 123 + 4 5 6 ! * 7 ! 8 / + * 9 / +

大致計算過程：

0入棧

！為運算符，計算棧頂0！，結果入棧

123入棧

+為運算符，將棧頂兩元素相加，結果入棧

4入棧

5入棧

6入棧

！為運算符，將棧頂6進行運算，結果入棧

*為運算符，將棧頂6！和5相乘，結果入棧

7入棧

！為運算符，計算7！，結果入棧

8入棧

/為運算符，將棧頂兩元素相除，結果入棧

+為運算符，將棧頂兩元素相加，結果入棧

*為運算符，將棧頂兩元素相乘，結果入棧

………………………………

以上用例來自清華大學計算機系鄧俊輝老師數據結構課程。