逆波兰表达式求值

简介: 逆波兰表达式求值

一:中缀表达式和逆波兰表达式

中缀表达式就是我们日常生活中的基本运算:

比如:1+(4*2)+3+(6/2)=15;

逆波兰表达式又称为后缀表达式;

而逆波兰表达式是计算器计算的原理,根据逆波兰表达式,计算器可以计算出结果15

二:力扣:逆波兰表达式求值

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

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

注意:

有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。

每个操作数(运算对象)都可以是一个整数或者另一个表达式。

两个整数之间的除法总是 向零截断 。

表达式中不含除零运算。

输入是一个根据逆波兰表示法表示的算术表达式。

答案及所有中间计算结果可以用 32 位 整数表示。

示例 1: 输入:tokens = [“2”,“1”,“+”,“3”,“*”] 输出:9 解释:该算式转化为常见的中缀算术表达式为:((2
= 9
示例 2: 输入:tokens = [“4”,“13”,“5”,“/”,“+”] 输出:6 解释:该算式转化为常见的中缀算术表达式为:(4
(13 / 5)) = 6
示例 3: 输入:tokens =
[“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 <= tokens.length <= 104
tokens[i] 是一个算符("+"、"-"、"*" 或 "/"),或是在范围 [-200, 200] 内的一个整数
1
2
逆波兰表达式: 逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。 平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * (
3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。 逆波兰表达式主要有以下两个优点:
去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中

二:原理:

题目描述:

给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。


利用数据结构中栈的相关知识;

我们在这里遍历字符串数组 tokens ,将拿到的每个数字因为 tokens是字符串数组,而我们要的是整数哦,所以要类型转换)依次放到栈中,如果遍历到了字符"+“,”-“,”“,”/",我们就从栈顶拿出两个元素,先拿到的作为右操作数,后拿到的作为左操作数,然后再将计算的结果入栈,遍历完成后,返回最终的结果即可。
举个例子:
后缀表达式为:1 2 3 * + 4 5 * 6 + 7 * +

首先将数字1 2 3 入栈,然后遇到了运算符 * 此时出栈3和2,3作为右操作数,2作为左操作数,将23的结果6入栈,

然后又遇到了运算符 ‘+’,在次出栈2个元素(6和1),将计算结果6+1=7入栈在最后一次出栈前,并未出栈),继续遍历,入栈4,5,遇到运算符

‘',出栈5和4,将计算结果(45=20)入栈,继续遍历,

6入栈,然后遇到运算符’+’ 6和 20出栈,将计算结果(6+20=26)入栈,继续遍历,7入栈,然后遇到运算符’',7和26出栈,将计算结果(726=182)入栈,此时遇到运算符’+',出栈,182和前面未出栈元素7,将计算结果入栈,此时字符串数组全部遍历,得到最终结果182+7=189。

结合下图更好的理解。


三:代码实现:

class Solution {
        public int evalRPN(String[] tokens) {
            Stack<Integer> stack=new Stack<>();
            int num=0;
            for(int i=0;i<tokens.length;i++){
                if(tokens[i].equals("+")||tokens[i].equals("-")||tokens[i].equals("*")||tokens[i].equals("/")){
                    int num2= stack.pop();
                    int num1=stack.pop();
                     switch(tokens[i]){
                        case "+":
                            num=num1+num2;
                            break;
                        case "-":
                            num=num1-num2;
                            break;
                        case "*":
                            num=num1*num2;
                            break;
                        case "/":
                            num=num1/num2;
                            break;
                    }
                    stack.push(num);
                }else{
                    int l=Integer.valueOf(tokens[i]);
                    stack.push(l);
                }
            }
            if(stack.empty()) {
                return num;
            }
            return stack.pop();
        }
    }
目录
相关文章
|
机器学习/深度学习 搜索推荐 算法
Learning Disentangled Representations for Recommendation | NIPS 2019 论文解读
近年来随着深度学习的发展,推荐系统大量使用用户行为数据来构建用户/商品表征,并以此来构建召回、排序、重排等推荐系统中的标准模块。普通算法得到的用户商品表征本身,并不具备可解释性,而往往只能提供用户-商品之间的attention分作为商品粒度的用户兴趣。我们在这篇文章中,想仅通过用户行为,学习到本身就具备一定可解释性的解离化的用户商品表征,并试图利用这样的商品表征完成单语义可控的推荐任务。
24097 0
Learning Disentangled Representations for Recommendation | NIPS 2019 论文解读
|
存储 JavaScript API
Vuex的魔法宝典:掌握State, Getters, Mutations和Actions,让状态管理不再是难题
【8月更文挑战第27天】Vuex是Vue.js应用程序的状态管理工具,通过集中式存储管理组件状态并确保状态按照预定义的规则发生变化。
310 0
|
分布式计算 资源调度 Hadoop
Hadoop【问题记录 03】【ipc.Client: Retrying connect to server:xxx/:8032+InvalidResourceRequestException】解决
【4月更文挑战第2天】Hadoop【问题记录 03】【ipc.Client: Retrying connect to server:xxx/:8032+InvalidResourceRequestException】解决
866 2
【Java每日一题,简单题】csp202203-3 风险人群筛查
【Java每日一题,简单题】csp202203-3 风险人群筛查
|
11月前
|
监控 安全 测试技术
构建高效精准测试平台:设计与实现全攻略
在软件开发过程中,精准测试是确保产品质量的关键环节。一个高效、精准的测试平台能够自动化测试流程,提高测试覆盖率,缩短测试周期。本文将分享如何设计和实现一个精准测试平台,从需求分析到技术选型,再到具体的实现步骤。
247 0
|
11月前
|
运维 Kubernetes Cloud Native
云原生之旅:容器化与微服务的融合
【10月更文挑战第28天】 在数字化转型的浪潮中,云原生技术如星辰般璀璨,引领着企业IT架构的未来。本文将带你穿梭于云原生的世界,探索容器化技术和微服务架构如何携手共舞,打造灵活、高效的应用部署和运维模式。我们将通过实际代码示例,揭示这股力量背后的奥秘,并展现它们是如何为现代软件开发带来革新。准备好了吗?让我们启航,驶向云原生技术的深海。
|
Cloud Native 关系型数据库 大数据
定川信息「川立方数治平台」通过PolarDB产品生态集成认证!
杭州定川信息技术有限公司「川立方数据治理一体化智能平台」通过PolarDB产品生态集成认证!
|
存储 Python
理解云存储的成本结构与计费模式
【6月更文挑战第1天】云存储成本结构复杂,包括存储容量、数据传输和请求次数的费用。计费模式多样,如按用量、订阅或峰值计费。通过Python示例展示了上传下载文件操作。理解并合理选择云存储方案,避免不必要的费用,成为云存储的明智使用者。一起来探索这个“魔法盒子”吧!
241 1
|
搜索推荐 C语言
C语言排序算法之冒泡排序
C语言排序算法之冒泡排序
125 0
|
SQL Java 数据库连接
spring声明式事务 @Transactional 不回滚的多种情况以及解决方案
spring声明式事务 @Transactional 不回滚的多种情况以及解决方案
459 0