逆波兰表达式求值(LeetCode 150)

简介: 逆波兰表达式求值(LeetCode 150)

逆波兰表达式求值(LeetCode 150)

Description

给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意:

  • 有效的算符为 +-×÷
  • 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

Sample Input 1

tokens = ["2","1","+","3","*"]

Sample Output 1

9

Sample Tips 1

该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

Sample Input 2

tokens = ["4","13","5","/","+"]

Sample Output 2

6

Sample Tips 2

该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

Sample Input 3

tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

Sample Output 3

22

Sample Tips 3

该算式转化为常见的中缀算术表达式为:

((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

Tips

  • 1 <= tokens.length <= 104
  • tokens[i] 是一个算符("+""-""*""/"),或是在范围 [-200, 200] 内的一个整数

逆波兰表达式:

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

  • 平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 )
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * )

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

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

算法思想:

栈与递归之间在某种程度上是可以转换的!

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

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

在进一步看,本题中每一个子表达式要得出一个结果,然后拿这个结果再进行运算,那么这岂不就是一个相邻字符串消除的过程,和删除字符串中的所有相邻重复项中的对对碰非常像。

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

例如: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.

C++代码如下:

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // 力扣修改了后台测试数据,需要用longlong
        stack<long long> st; 
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                long long num1 = st.top();
                st.pop();
                long long 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(stoll(tokens[i]));
            }
        }

        int result = st.top();
        st.pop(); // 把栈里最后一个元素弹出(其实不弹出也没事)
        return result;
    }
};

Java代码代码如下:

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList();
        for (String s : tokens) {
            if ("+".equals(s)) {        // leetcode 内置jdk的问题,不能使用==判断字符串是否相等
                stack.push(stack.pop() + stack.pop());      // 注意 - 和/ 需要特殊处理
            } else if ("-".equals(s)) {
                stack.push(-stack.pop() + stack.pop());
            } else if ("*".equals(s)) {
                stack.push(stack.pop() * stack.pop());
            } else if ("/".equals(s)) {
                int temp1 = stack.pop();
                int temp2 = stack.pop();
                stack.push(temp2 / temp1);
            } else {
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }
}
目录
相关文章
|
IDE 数据可视化 Java
5款经典代码阅读器的使用方案对比
代码阅读是技术人的必备技能之一,高效地梳理代码能够极大程度上提高开发人员的工作效率,进一步为业务创造新价值。
12200 0
5款经典代码阅读器的使用方案对比
RuntimeError: Given groups=1, weight of size 64 128 1 7, expected input[16,
RuntimeError: Given groups=1, weight of size 64 128 1 7, expected input[16,
3255 0
|
10月前
|
人工智能 自然语言处理 安全
已解决:Poe AI国内能用吗?国内用户如何使用Poe AI?亲测有效的方法来了!
人工智能正在重塑我们的世界,而Poe AI作为AI聊天机器人平台的佼者,更是引领着这场变革。它集成了众多顶尖AI模型,如OpenAI的GPT系列、Anthropic的Claude系列以及Google的PaLM等,为用户提供了一个探索AI无限可能的开放平台
553 12
|
10月前
|
人工智能 自然语言处理 安全
在线使用:Poe Ai网页版_pc版_poe ai中文官网入口
幸运的是,如今国内用户也可以轻松享受Poe AI的强大功能,突破网络屏障,开启属于自己的AI创作之旅!
1549 7
在线使用:Poe Ai网页版_pc版_poe ai中文官网入口
|
10月前
|
开发框架 缓存 .NET
GraphQL 与 ASP.NET Core 集成:从入门到精通
本文详细介绍了如何在ASP.NET Core中集成GraphQL,包括安装必要的NuGet包、创建GraphQL Schema、配置GraphQL服务等步骤。同时,文章还探讨了常见问题及其解决方法,如处理复杂查询、错误处理、性能优化和实现认证授权等,旨在帮助开发者构建灵活且高效的API。
227 3
|
运维 Devops
全球与中国DevOps市场现状及未来发展趋势
本文研究全球及中国市场DevOps现状及未来发展趋势,侧重分析全球及中国市场的主要企业,同时对比北美、欧洲、中国、日本、东南亚和印度等地区的现状及未来发展趋势
全球与中国DevOps市场现状及未来发展趋势
|
12月前
|
存储 安全 程序员
【C++篇】深入内存迷宫:C/C++ 高效内存管理全揭秘
【C++篇】深入内存迷宫:C/C++ 高效内存管理全揭秘
626 3
|
缓存 Java Nacos
nacos服务注册问题之容器报错如何解决
Nacos是一个开源的、易于部署的动态服务发现、配置管理和服务管理平台,旨在帮助微服务架构下的应用进行快速配置更新和服务治理;在实际运用中,用户可能会遇到各种报错,本合集将常见的Nacos报错问题进行归纳和解答,以便使用者能够快速定位和解决这些问题。
782 107
|
安全 监控 网络安全
HW蓝队面试题精选
该内容是关于网络安全面试的题型,涵盖了网络安全的多个重要方面。
357 4
|
运维 网络安全 Python
使用Python http.server模块共享文件
今天给大家介绍一下Python标准库中的http.server模块。这个模块提供了一种简单的方式来快速启动一个HTTP服务器,非常适合临时共享文件、测试、教学等轻量级场景。