6/7 算法题详解:Evaluate RPN Expressions 如何求逆波兰表达式(RPN)的值


(caozihua) #1

本视频来自于北美CS刷题神器BitTiger Pro


首先我们先来看一下什么是RPN表达式。RPN全称逆波兰表示法(Reverse Polish Notation)。RPN也被称为后缀表示法,RPN表达式不同于我们日常见到的表达式,它的所有操作符置于操作数的后面,故而逆波兰记法不需要括号来标识操作符的优先。当满足以下两个条件,我们就可以称一个表达式为RPN表达式:

  1. 它是由单个数字或者带有负号的数字序列,比如-23,123
  2. 它是以“A B OP”形式展现的,其中A,B是RPN表达式,OP是运算符+、-、*和/。

比方说“三加四”用RPN的方式就写作“3 ,4 +”。我们可以很明显地看到我们熟悉的加号被放到了后面,这就是RPN表达式显著的特征。

事实上RPN表达式可以被构造成一棵二叉树,比方说RPN表达式“3,4,+,2,*,1,+”,它的树结构就如下图所示:

![](data:image/svg+xml;utf8,)

图中,3和4构成了最小最底层的树结构,然后乘以2构成了上一层的数,最后加上1形成了完整的二叉树。

为了让你更加了解RPN表达式,下面给出一些例子,大家动手试着把他们转化为我们平时在使用的表达式。

![](data:image/svg+xml;utf8,)

在计算机科学编程者中,RPN表达式非常流行。当给出的是一般的计算表达式,经常转化为RPN表达式来执行计算。原因显而易见,从编程角度看,RPN表示式是一种更加简单的格式。

让我们开始讲解如何实现RPN表示式的计算。还是举例说明,比如“3,4,+,2,,1,+”。我们从左到右开始计算这个表达式,首先我们读取3和4,然后得到一个“+”,计算3加4的结果,是7,作为临时结果,然后继续读取,2和“”,就将临时结果7乘以2,得到临时结果14,最后读取1和“+”,将14加1,得到最终结果15。

在这几步计算中我们发现:

  1. 我们需要存储临时结果;
  2. 当我们读取到运算符,就需要申请最近获得的两个数字(包括临时结果和读取的数字),临时结果的插入和删除执行“后入先出(last-in,first-out)”的原则。

从上述发现我们可以用堆(stack)可以很好的满足RPN表达式的计算场景。

我们给出的解决方案就是从左到右扫描字符串,使用堆的思想实现,当我们读取到操作数(operand),push到堆顶,当我们读取到操作符(operator),从堆顶pull出最上面的2个数字,进行计算,然后把结果在push到堆顶。

让我们来看一个例子:

  • 读取第一个字符,是1,它是一个数字,所以把它push到堆里。

![](data:image/svg+xml;utf8,)

  • 读取下一个字符,是2,它是一个数字,所以把它push到堆里。

![](data:image/svg+xml;utf8,)

  • 读取下一个字符,是3,它是一个数字,所以把它push到堆里。

![](data:image/svg+xml;utf8,)

  • 读取下一个字符,是4,它是一个数字,所以把它push到堆里。

![](data:image/svg+xml;utf8,)

  • 读取下一个字符,是“+”,它是一个运算符,按照我们的算法,需要把堆顶的两个元素拿出来进行计算,得到局部结果7。

![](data:image/svg+xml;utf8,)

  • 把局部结果7 push到堆顶。

![](data:image/svg+xml;utf8,)

  • 接下来到了第二个运算符,还是加号,需要把堆顶的两个元素拿出来进行计算,得到局部结果9。

![](data:image/svg+xml;utf8,)

  • 把局部结果9 push到堆顶。

![](data:image/svg+xml;utf8,)

  • 接下来到了第三个运算符,还是加号,需要把堆顶的两个元素拿出来进行计算,得到最终结果10。

![](data:image/svg+xml;utf8,)

实现代码如下:

![](data:image/svg+xml;utf8,)

需要说明一下,在前文中我们提到需要使用堆来实现,但是在实际实现中,我们采用了Deque(双端队列,全名double-ended queue)来实现。事实上Deque是Java中一种普遍实现堆的方法。

回头看一下代码,首先中我们把传入的表达式进行切割,然后是借助分隔好的字符串数组进行循环,如果是数字,那就push到堆里面,如果是运算符,按照运算符的类型分情况执行。等到数组访问完,就返回最后一个堆里面的元素。

最后我们分析一下性能。时间复杂度是O(n),比较好理解,我们就是遍历整个字符串。空间复杂度是O(n),因为我们需要把每个原始数据和临时结果存下来。


本视频来自于北美CS刷题神器BitTiger Pro

每月更新的BitTiger Pro是一个覆盖了CS和数据科学方向最新高频面试题的精讲视频库。订阅后,你可以在Code Evaluation System亲自练习这道题。

![](data:image/svg+xml;utf8,)