每天一算:Evaluate Reverse Polish Notation

LeetCode上第150号问题:逆波兰表达式求值

题目

根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 说明: 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。 示例 1: 输入: ["2", "1", "+", "3", "*"] 输出: 9 解释: ((2 + 1) * 3) = 9 示例 2: 输入: [“4”, “13”, “5”, “/“, “+”] 输出: 6 解释: (4 + (13 / 5)) = 6 示例 3: 输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] 输出: 22 解释: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22

解题思路

用数据结构来解决这个问题。

  • 从前往后遍历数组
  • 遇到数字则压入栈中
  • 遇到符号,则把栈顶的两个数字拿出来运算,把结果再压入栈中
  • 遍历完整个数组,栈顶数字即为最终答案

动画演示

动画演示GIF加载有点慢,请稍待片刻加载显示^_^

参考代码

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

原文发布于微信公众号 - 五分钟学算法(blgczzz)

原文发表时间:2018-11-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏swag code

抽象类与抽象方法

在我们抽象实例对象的时候,有这样一种情况,往上层抽象时就会发现很难描述对象的属性和行为,比如“形状” ,其方法计算面积怎么计算?正方形知道怎么计算,长方形也知道...

773
来自专栏蓝天

彻底理解C/C++指针

彻底理解C++指针.pdf 推荐阅读pdf版本,原因是从WPS复制粘贴到ChinaUnix后格式有些丢了。

881
来自专栏海天一树

AtCoder入门练习题B--题解报告

一、题目 https://practice.contest.atcoder.jp/tasks/practice_2 二、分析 这里有三组测试用例。 第一组N =...

3208
来自专栏noteless

[一]基础类型概述

https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html

1083
来自专栏程序员互动联盟

【编程基础】C语言循环语句解析

循环语句是一种很重要的结构,这种结构的特点就是在某种条件下,会重复循环执行某一段代码,直到条件不成立为止。这里的条件称为循环条件,重复执行的那段代码称为循环体。...

3685
来自专栏Python小屋

妙用Python内置函数int()快速计算等比数列前n项和

本文要点在于Python内置函数int()的用法,所以计算等比数列前n项和时没有使用数学上的公式Sn=a1*(1-q^n)/(1-q)。 一般遇到这样的问题,很...

5066
来自专栏积累沉淀

JavaScript面向对象与原型

javaScript有两种开发模式:1.函数式(过程化),2.面向对象(OOP)。面向对象的语言有一个标志,那就是类的概念,而通过类可以创建任意多个具有相同属性...

21710
来自专栏小小挖掘机

各种排序算法的分析及java&python实现

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

3877
来自专栏武培轩的专栏

排序算法-冒泡排序

算法简介 冒泡排序(Bubble Sort)是一种典型的交换排序算法,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。 算法描述 比较相邻的...

3457
来自专栏章鱼的慢慢技术路

浅谈main(),int main(),void main(),int main(void)四者之间的区别

1173

扫码关注云+社区