数据结构和算法基础篇（六）逆波兰式

上一篇中，我们讲解了一道使用两个栈实现具有最小值功能的栈，当然也可以实现具有最大值功能的栈。本期我们继续讲解栈的应用场景。

我们以Leetcode 424题为例，这是一道逆波兰式的求解问题。在Leetcode上，这道题目是标注为中等难度的，决绝这个难度的题目大部分互联网公司可以去了。

当然，成为一名优秀的算法工程师，这个题目只是基础的题目了。

首先我们介绍一下，什么叫做逆波兰式。这里读者可以自己去百度看看专业的解释。

所谓的逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

举个简单的例子，平常我们写的数学表达式a+b，就是一种中缀表达式，写成后缀表达式就是ab+。再举一个复杂的例子，中缀表达式(a+b)*c-(a+b)/e的逆波兰式是ab+c*ab+e/-。

424. 逆波兰表达式求值（中等难度）

题目：在逆波兰表达法中，其有效的运算符号包括 , , , 。每个运算对象可以是整数，也可以是另一个逆波兰计数表达。

样例

思考：我们发现，当遇到数字，就不计算，遇到运算符，就取前运算符前面的两个数字进行计算，计算结果保存进去。

这样我们得到解决思路就是，遇到数字就压栈，遇到运算符就去取出两个数字进行运算，运算结构继续放入栈中，这样我们开始我们的代码。

首先，由于输入的每个元素字符串我们需要判断是字符还是运算符号。

注意处理“-3”这样也是数字。

下面我们再看一道高难度的题目。

370. 将表达式转换为逆波兰表达式

描述

给定一个表达式字符串数组，返回该表达式的逆波兰表达式（即去掉括号）。

样例

对于 的表达式（该表达式可表示为["3", "-", "4", "+", "5"]），返回 （该表达式可表示为 ["3", "4", "-", "5", "+"]）。

题目的要求其实就是将中缀表达式转化为逆波兰式（后缀表示法）。

下一篇文章我们贴上代码。