专栏首页五分钟学算法每天一算:Evaluate Reverse Polish Notation

每天一算: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),作者:菠了个菜

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 10% + 10% = 0.11 ?是 bug 还是 feature ?微软开源的计算器项目告诉你答案!

    近日,关于手机计算器10%+10%=0.11的事情火热,多个品牌的手机未能幸免,基本“阵亡”,同时还包括了windows10的自带标准计算器。你的手机阵亡了吗?

    五分钟学算法
  • 法解种三的数文回:画动

    判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

    五分钟学算法
  • 好吧,又是两分钟看完一道投机取巧的算法题

    事实上,你在使用暴力破解法的过程中就能发现规律: 这 9 个数字中只有 2(它的倍数) 与 5 (它的倍数)相乘才有 0 出现。

    五分钟学算法
  • Jax:有望取代Tensorflow,谷歌出品的又一超高性能机器学习框架

    在机器学习框架方面,JAX是一个新生事物——尽管Tensorflow的竞争对手从技术上讲已经在2018年后已经很完备,但直到最近JAX才开始在更广泛的机器学习研...

    HuangWeiAI
  • C# dotnet 高性能多线程工具 ExecuteOnceAwaiter 只执行一次的任务

    本文将安利大家一个好用的工具,用来解决这样的问题,我有一个任务,要求这个任务在执行过程中不能被重入,只有在任务执行完成之后才能重置状态重新执行一次。换句话说就是...

    林德熙
  • 智能机器人机械手臂原理图

    电源模块原理图 ? 手爪旋转模块原理图 ? 手爪张合模块原理图 ? ? ? ?

    机器人网
  • 微信小程序的技术架构特点

    腾讯为微信小程序的工程项目开发了完整的编辑开发、运行调试、打包发布环境,形成了一个完整的IDE。

    用户6117737
  • 小程序一周报 | 小程序游戏类目开放测试 / 朋友圈小程序广告全量上线

    极乐君
  • 微信小程序从使用到分析快速解析

    新功能意味着更低的使用门槛——个人注册、更多的流量通道——可借助线下已有二维码与APP链接、更多的触达手段——公众号绑定。这些是不是让很多人心中蠢蠢欲动,感觉又...

    腾讯大数据
  • 小程序,互联网的第五大发明

    凡连接就涉及到连接哪两个主体,以及在这两个主体之间用什么形式和密度去连接。比如新航道的发现、新大陆的发现,海上丝绸之路,两个城市之间的高速公路,航空公司之间的连...

    中微信通

扫码关注云+社区

领取腾讯云代金券