面試官：請您說說怎么計算四則運算？比如1 + 2 * ( 3 + 4 ) - 5，
我：先算括號里再算括號外，先乘除后加減，最后等于10，
面試官懵了一下，說：可能我說明白，我想問的是用計算機怎么計算？
我尬尷的笑了笑，馬上說到：對于計算機來說，單純的兩個數的加減乘除很容易，但是如果乘除在加減的后面卻要先運算，再加上幾個括號，就變得更加復雜了，
為了使計算機更容易理解，前人已為我們引入了一種新的四則運算的表示法，
逆波蘭式
有一位波蘭數學家名字叫：揚·武卡謝維奇（Jan ?ukasiewicz），就是這位：
他在1920年引入一種新的數學運算式形式：逆波蘭式（Reverse Polish notation，RPN，或逆波蘭記法），在逆波蘭式中，不需要括號來標識運算子的優先級，所有運算子都放在運算元的后面，因此也被稱為后綴表達法，我們在小學時經常用的是中綴表達法，也就是運算子在運算元之間，比如：1 + 2 * ( 3 + 4 ) - 5，對應的逆波蘭式就是：1 2 3 4 + * + 5 -，
逆波蘭式的計算
根據逆波蘭式計算結果，需要借助堆疊（Stack）這種資料結構，堆疊（Stack）是限定僅在表尾進行插入或洗掉操作的線性表，遵循后進先出（Last In First Out，LIFO）的原則，
具體步驟如下：
- 從左到右掃描運算式，如果當前字符為數字，則入堆疊，
- 如果當前字符為運算子，則將堆疊頂兩個元素出堆疊，作相應運算，結果再入堆疊，
- 最后當運算式掃描完后，堆疊里的就是計算結果了，
我們以1 2 3 4 + * + 5 -為例：
| 輸入 | 操作 | 堆疊 | 注釋 |
|---|---|---|---|
| 1 | 入堆疊 | 1 | |
| 2 | 入堆疊 | 1，2 | |
| 3 | 入堆疊 | 1，2，3 | |
| 4 | 入堆疊 | 1，2，3，4 | |
| + | 加法運算 | 1，2，7 | 3，4出堆疊，將結果7入堆疊 |
| * | 乘法運算 | 1，14 | 2，7出堆疊，將結果14入堆疊 |
| + | 加法運算 | 15 | 1，14出堆疊，將結果15入堆疊 |
| 5 | 入堆疊 | 15，5 | |
| - | 減法運算 | 10 | 15，5出堆疊，將結果10入堆疊 |
最終的計算結果為：10，
逆波蘭式的轉換
計算機可以根據逆波蘭式計算出結果，那么問題來了！我們常用的中綴表達法怎么轉換成逆波蘭式呢？也是需要借助堆疊這種資料結構，具體步驟如下：
- 從左到右掃描中綴運算式，如果當前字符為數字就直接輸出，
- 如果當前字符為運算子，則判斷其與堆疊頂運算子的優先級，
- 如果是右括號或者優先級低于堆疊頂運算子，則堆疊內運算子依次出堆疊并輸出，然后當前運算子入堆疊，
- 最后當中綴運算式掃描完后，輸出的就是逆波蘭式了，
我們以1 + 2 * ( 3 + 4 ) - 5為例：
| 輸入 | 操作 | 堆疊 | 輸出 |
|---|---|---|---|
| 1 | 輸出 | 1 | |
| + | 入堆疊 | + | 1 |
| 2 | 輸出 | + | 1 2 |
| * | 入堆疊 | +，* | 1 2 |
| ( | 入堆疊 | +，*，( | 1 2 |
| 3 | 輸出 | +，*，( | 1 2 3 |
| + | 入堆疊 | +，*，(，+ | 1 2 3 |
| 4 | 輸出 | +，*，(，+ | 1 2 3 4 |
| ) | 依次出堆疊至( | +，* | 1 2 3 4 + |
| - | 依次出堆疊，然后-入堆疊 | - | 1 2 3 4 + * + |
| 5 | 輸出 | - | 1 2 3 4 + * + 5 |
| 依次出堆疊 | 1 2 3 4 + * + 5 - |
最終的逆波蘭式為：1 2 3 4 + * + 5 -，
看著面試官滿意的笑容，我擦了擦額頭汗，還好我夠機靈，
微信公眾號：萬貓學社
微信掃描二維碼
關注后回復「電子書」
獲取12本Java必讀技術書籍
最后，感謝你的點贊和關注，帥氣又美麗，
作者：萬貓學社
出處：http://www.cnblogs.com/heihaozi/
著作權宣告：本文遵循 CC 4.0 BY-NC-SA 著作權協議，轉載請附上原文出處鏈接和本宣告，
微信掃描二維碼，關注萬貓學社，回復「電子書」，免費獲取12本Java必讀技術書籍，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/424875.html
標籤：Java