专栏首页代码随想录栈与队列:有没有想过计算机是如何处理表达式的?

栈与队列:有没有想过计算机是如何处理表达式的?

本文:https://github.com/youngyangyang04/leetcode-master​已经收录,里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图,可以fork到自己仓库,有空看一看一定会有所收获,如果对你有帮助也给一个star支持一下吧!

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

逆波兰表达式:是一种后缀表达式,所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点:

  • 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中。

思路

在上一篇文章中栈与队列:匹配问题都是栈的强项提到了 递归就是用栈来实现的。

所以「栈与递归之间在某种程度上是可以转换的」,这一点我们在后续讲解二叉树的时候,会更详细的讲解到。

那么来看一下本题,「其实逆波兰表达式相当于是二叉树中的后序遍历」。大家可以把运算符作为中间节点,按照后序遍历的规则画出一个二叉树。

但我们没有必要从二叉树的角度去解决这个问题,只要知道逆波兰表达式是用后续遍历的方式把二叉树序列化了,就可以了。

在进一步看,本题中每一个子表达式要得出一个结果,然后拿这个结果再进行运算,那么「这岂不就是一个相邻字符串消除的过程,和栈与队列:匹配问题都是栈的强项中的对对碰游戏是不是就非常像了。」

如动画所示:

相信看完动画大家应该知道,这和1047. 删除字符串中的所有相邻重复项是差不错的,只不过本题不要相邻元素做消除了,而是做运算!

代码如下:

C++代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                if (tokens[i] == "+") st.push(num2 + num1);
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            } else {
                st.push(stoi(tokens[i]));
            }
        }
        int result = st.top();
        st.pop(); // 把栈里最后一个元素弹出(其实不弹出也没事)
        return result;
    }
};

题外话

我们习惯看到的表达式都是中缀表达式,因为符合我们的习惯,但是中缀表达式对于计算机来说就不是很友好了。

例如:4 + 13 / 5,这就是中缀表达式,计算机从左到右去扫描的话,扫到13,还要判断13后面是什么运算法,还要比较一下优先级,然后13还和后面的5做运算,做完运算之后,还要向前回退到 4 的位置,继续做加法,你说麻不麻烦!

那么将中缀表达式,转化为后缀表达式之后:["4", "13", "5", "/", "+"] ,就不一样了,计算机可以利用栈里顺序处理,不需要考虑优先级了。也不用回退了, 「所以后缀表达式对计算机来说是非常友好的。」

可以说本题不仅仅是一道好题,也展现出计算机的思考方式。

在1970年代和1980年代,惠普在其所有台式和手持式计算器中都使用了RPN(后缀表达式),直到2020年代仍在某些模型中使用了RPN。

参考维基百科如下:

During the 1970s and 1980s, Hewlett-Packard used RPN in all of their desktop and hand-held calculators, and continued to use it in some models into the 2020s.

在留言区留下你的思路吧!

-------end-------

我是程序员Carl,哈工大师兄,先后在腾讯和百度从事技术研发多年,利用工作之余重刷leetcode。

我的B站(里面有我讲解的算法视频以及编程相关知识):https://space.bilibili.com/525438321

我的githubhttps://github.com/youngyangyang04

更多 精彩算法文章尽在:代码随想录,关注后,回复「Java」「C++」「python」「简历模板」等等,有我整理多年的学习资料,可以加我  微信,备注「个人简介」+「组队刷题」,拉你进入刷题群(无任何广告,纯个人分享),每天一道经典题目分析,我选的每一道题目都不是孤立的,而是由浅入深一脉相承的,如果跟住节奏每篇连续着看,定会融会贯通。

本文分享自微信公众号 - 代码随想录(code_thinking),作者:程序员Carl

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

原始发表时间:2020-09-16

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二叉树:前中后序迭代方式的写法就不能统一一下么?

    此时我们在二叉树:一入递归深似海,从此offer是路人中用递归的方式,实现了二叉树前中后序的遍历。

    代码随想录
  • 数组:总结篇

    数组是非常基础的数据结构,在面试中,考察数组的题目一般在思维上都不难,主要是考察对代码的掌控能力

    代码随想录
  • 本周小结!(二叉树)

    发现大家周末的时候貌似都不在学习状态,周末的文章浏览量和打卡情况照工作日差很多呀,可能是本周日是工作日了,周六得好好放松放松,哈哈,理解理解,但我还不能不更啊,...

    代码随想录
  • Java代码审计之SpEL表达式注入

    Spring Expression Language(简称 SpEL)是一种功能强大的表达式语言、用于在运行时查询和操作对象图;语法上类似于 Unified E...

    FB客服
  • 15、web爬虫讲解2—urllib库中使用xpath表达式—BeautifulSoup基础

    在urllib中,我们一样可以使用xpath表达式进行信息提取,此时,你需要首先安装lxml模块,然后将网页数据通过lxml下的etree转化为treedata...

    天降攻城狮
  • 知识扩展——(转)一篇文章彻底弄懂Base64编码原理

      在互联网中的每一刻,你可能都在享受着Base64带来的便捷,但对于Base64的基础原理又了解多少?今天这篇博文带领大家了解一下Base64的底层实现。

    mukekeheart
  • 小朋友学C++(18):标准库vector类

    vector(向量)是 C++中的一种数据结构,也是一个类。它相当于一个动态的数组,当程序员无法知道自己需要的数组的规模多大时,用其来解决问题可以达到最大节约空...

    海天一树
  • 【LeetCode】225. 用队列实现栈

    push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空 注意:

    韩旭051
  • 从0到1开发测试平台(七)后端服务添加swagger第三方类库

    swagger 是一个规范和完整的框架,用于生成、描述、调用和可视化 RESTful 风格的 Web 服务。简单来说就是一个生成接口文档的第三方类库。

    cctester
  • 如何在腾讯云COS部署HEXO博客

    前段时间发现我的博客老是报456错误,而且国内速度加载越来越慢,不知道是什么问题,打算优化下。正在我查资料的时候,突然发现,腾讯云COS竟然支持静态网站部署了,...

    Techeek

扫码关注云+社区

领取腾讯云代金券