没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全[宫水三叶的刷题日记]：表达式计算问题1

[宫水三叶的刷题日记]：表达式计算问题1

需积分: 0 0 下载量 98 浏览量 2022-08-03 11:16:26 上传评论收藏 1.72MB PDF 举报

温馨提示

试读

27页

2. 从侧边栏的类别目录找到「表达式计算问题」 3. 按照「推荐指数」从大到小进行刷题，「推荐指数」相同，则按照「难度」从易到 4. 拿到题号之后，回到本合集进

资源详情

资源评论

资源推荐

🍭

更多精彩内容，欢迎关注：公众号 / Github / LeetCode / 知乎 **

噔噔噔噔，这是公众号「噔噔噔噔，这是公众号「宫水三叶的刷宫水三叶的刷题题日日记记」的原」的原创专题创专题「表达式「表达式计计算算问题问题」合集。」合集。

本合集更新时间本合集更新时间为为 2021-10-07，大概每，大概每 2-4 周会集中更新一次。周会集中更新一次。关注公众号，后台回复「表达注公众号，后台回复「表达

式式计计算算问题问题」即可获取最新下」即可获取最新下载链载链接。接。

💡💡

下面介下面介绍绍使用本合集的最佳使用实使用本合集的最佳使用实践：：

学学习习算法：算法：

1. 打开在线目录（Github 版 & Gitee 版）；

2. 从侧边栏的类别目录找到「表达式计算问题」；

3. 按照「推荐指数」从大到小进行刷题，「推荐指数」相同，则按照「难度」从易到

难进行刷题‘

4. 拿到题号之后，回到本合集进行检索。

维维持熟持熟练练度：度：

1. 按照本合集「从上往下」进行刷题。

学学习习过程中遇到任何困过程中遇到任何困难难，欢迎加入「每日一，欢迎加入「每日一题题打卡打卡 QQ 群：群：703311589」」进进行交流行交流

🍭🍭🍭🍭🍭🍭

🍭

更多精彩内容，欢迎关注：公众号 / Github / LeetCode / 知乎 **

题题目描述目描述

这是 LeetCode 上的 150. 逆波逆波兰兰表达式求值表达式求值，难度为中等中等。

Tag : 「表达式计算」

根据逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

• 整数除法只保留整数部分。

• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数

为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]

输出：9

解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 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 <= 10

• tokens[i] 要么是一个算符（"+"、"-"、"*" 或 “/”），要么是一个在范围 [-200, 200]

内的整数

逆波兰表达式：

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

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

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

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

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确

结果。

• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并

将结果压入栈中。

基本思路基本思路

这是一道关于「表达式计算」的题目。

所有的「表达式计算」问题都离不开「栈」。

对于本题，我们可以建立一个「数字栈」，存放所有的数字，当遇到运算符时，从栈中取出两个

数进行运算，并将结果放回栈内，整个过程结束后，栈顶元素就是最终结果。

而栈的实现通常有两种：使用数组继续模拟 & 使用系统自带的栈结构

数数组组模拟模拟栈栈解法解法

代码：

class Solution {

public int evalRPN(String[] ts) {

int[] d = new int[ts.length];

int hh = 0, tt = -1;

for (String s : ts) {

if ("+-*/".contains(s)) {

int b = d[tt--], a = d[tt--];

d[++tt] = calc(a, b, s);

} else {

d[++tt] = Integer.parseInt(s);

}

return d[tt];

}

int calc(int a, int b, String op) {

if (op.equals("+")) return a + b;

else if (op.equals("-")) return a - b;

else if (op.equals("*")) return a * b;

else if (op.equals("/")) return a / b;

else return -1;

}

• 时间复杂度：O(n)

• 空间复杂度：O(n)

剩余26页未读，继续阅读

内容反馈

好运爆棚

粉丝: 31
资源: 342

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

[宫水三叶的刷题日记]：表达式计算问题1

评论0

最新资源

[宫水三叶的刷题日记]：表达式计算问题1

评论0

[宫水三叶的刷题日记]：数学1

[宫水三叶的刷题日记]：BFS1

[宫水三叶的刷题日记]：分治1

[宫水三叶的刷题日记]：DFS1

[宫水三叶的刷题日记]：n 数之和1

[宫水三叶的刷题日记]：单调栈1

[宫水三叶的刷题日记]：状压 DP1

[宫水三叶的刷题日记]：括号问题1

[宫水三叶的刷题日记]：排序1

[宫水三叶的刷题日记]：位运算1

[宫水三叶的刷题日记]：模拟1

[宫水三叶的刷题日记]：堆1

[宫水三叶的刷题日记]：三分1

[宫水三叶的刷题日记]：栈1

[宫水三叶的刷题日记]：树状数组1

[宫水三叶的刷题日记]：线段树1

[宫水三叶的刷题日记]：并查集1

[宫水三叶的刷题日记]：（图论）BFS1

[宫水三叶的刷题日记]：数独问题1

[宫水三叶的刷题日记]：博弈论1

[宫水三叶的刷题日记]：哈希表1

[宫水三叶的刷题日记]：回文串问题1

[宫水三叶的刷题日记]：扫描线问题1

[宫水三叶的刷题日记]：双指针1

[宫水三叶的刷题日记]：（图论）拓扑排序1

[宫水三叶的刷题日记]：（图论）最小生成树1

[宫水三叶的刷题日记]：组合总和问题1

[宫水三叶的刷题日记]：队列1

[宫水三叶的刷题日记]：二叉树1

最新资源