昨天去某大厂面试，居然让我做四则运算，还好我够机灵。

淩亂°似流年 2022-10-21 03:43 16阅读 0赞

面试官：请您说说怎么计算四则运算？比如`1 + 2 * ( 3 + 4 ) - 5`。

我：先算括号里再算括号外，先乘除后加减，最后等于10。

面试官懵了一下，说：可能我说明白，我想问的是用计算机怎么计算？

我尬尴的笑了笑，马上说到：对于计算机来说，单纯的两个数的加减乘除很容易，但是如果乘除在加减的后面却要先运算，再加上几个括号，就变得更加复杂了。

为了使计算机更容易理解，前人已为我们引入了一种新的四则运算的表示法。

### 逆波兰式 ###

有一位波兰数学家名字叫：扬·武卡谢维奇（Jan Łukasiewicz），就是这位：

![Jan Łukasiewicz][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.  最后当表达式扫描完后，栈里的就是计算结果了。

我们以`1 2 3 4 + * + 5 -`为例：

最终的计算结果为：10。

### 逆波兰式的转换 ###

计算机可以根据逆波兰式计算出结果，那么问题来了！我们常用的中缀表达法怎么转换成逆波兰式呢？也是需要借助栈这种数据结构，具体步骤如下：

1.  从左到右扫描中缀表达式，如果当前字符为数字就直接输出。
2.  如果当前字符为运算符，则判断其与栈顶运算符的优先级。
3.  如果是右括号或者优先级低于栈顶运算符，则栈内运算符依次出栈并输出，然后当前运算符入栈。
4.  最后当中缀表达式扫描完后，输出的就是逆波兰式了。

我们以`1 + 2 * ( 3 + 4 ) - 5`为例：

<table> 
 <thead> 
  <tr> 
   <th align="center">输入</th> 
   <th align="left">操作</th> 
   <th align="left">堆栈</th> 
   <th align="left">输出</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">1</td> 
   <td align="left">输出</td> 
   <td align="left"></td> 
   <td align="left">1</td> 
  </tr> 
  <tr> 
   <td align="center">+</td> 
   <td align="left">入栈</td> 
   <td align="left">+</td> 
   <td align="left">1</td> 
  </tr> 
  <tr> 
   <td align="center">2</td> 
   <td align="left">输出</td> 
   <td align="left">+</td> 
   <td align="left">1 2</td> 
  </tr> 
  <tr> 
   <td align="center">*</td> 
   <td align="left">入栈</td> 
   <td align="left">+，*</td> 
   <td align="left">1 2</td> 
  </tr> 
  <tr> 
   <td align="center">(</td> 
   <td align="left">入栈</td> 
   <td align="left">+，*，(</td> 
   <td align="left">1 2</td> 
  </tr> 
  <tr> 
   <td align="center">3</td> 
   <td align="left">输出</td> 
   <td align="left">+，*，(</td> 
   <td align="left">1 2 3</td> 
  </tr> 
  <tr> 
   <td align="center">+</td> 
   <td align="left">入栈</td> 
   <td align="left">+，*，(，+</td> 
   <td align="left">1 2 3</td> 
  </tr> 
  <tr> 
   <td align="center">4</td> 
   <td align="left">输出</td> 
   <td align="left">+，*，(，+</td> 
   <td align="left">1 2 3 4</td> 
  </tr> 
  <tr> 
   <td align="center">)</td> 
   <td align="left">依次出栈至(</td> 
   <td align="left">+，*</td> 
   <td align="left">1 2 3 4 +</td> 
  </tr> 
  <tr> 
   <td align="center">-</td> 
   <td align="left">依次出栈，然后-入栈</td> 
   <td align="left">-</td> 
   <td align="left">1 2 3 4 + * +</td> 
  </tr> 
  <tr> 
   <td align="center">5</td> 
   <td align="left">输出</td> 
   <td align="left">-</td> 
   <td align="left">1 2 3 4 + * + 5</td> 
  </tr> 
  <tr> 
   <td align="center"></td> 
   <td align="left">依次出栈</td> 
   <td align="left"></td> 
   <td align="left">1 2 3 4 + * + 5 -</td> 
  </tr> 
 </tbody> 
</table>

最终的逆波兰式为：`1 2 3 4 + * + 5 -`。

看着面试官满意的笑容，我擦了擦额头汗，还好我够机灵。

> 感谢帅哥靓女的**关注**、**收藏**、**点赞**！

> 文章持续更新，微信搜索「**万猫学社**」第一时间阅读。  
> 关注后回复「**电子书**」，免费获取12本Java必读技术书籍。

[Jan _ukasiewicz]: /images/20221021/4d0a2a50428f45a7addfdff79c137c62.png