手记

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

面试官:请您说说怎么计算四则运算?比如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. 最后当表达式扫描完后,栈里的就是计算结果了。

我们以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. 最后当中缀表达式扫描完后,输出的就是逆波兰式了。

我们以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 -

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

最后,感谢你的点赞推荐关注,帅气又美丽。

2人推荐
随时随地看视频
慕课网APP