逆波兰表达式求值
难度:
标签:
题目描述
给你一个字符串数组 tokens
,表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意:
- 有效的算符为
'+'
、'-'
、'*'
和'/'
。 - 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 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 <= 104
tokens[i]
是一个算符("+"
、"-"
、"*"
或"/"
),或是在范围[-200, 200]
内的一个整数
逆波兰表达式:
逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式,如
( 1 + 2 ) * ( 3 + 4 )
。 - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )
。
逆波兰表达式主要有以下两个优点:
- 去掉括号后表达式无歧义,上式即便写成
1 2 + 3 4 + *
也可以依据次序计算出正确结果。 - 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中
代码结果
运行时间: 19 ms, 内存: 17.5 MB
/*
* 题目思路:
* 1. 使用Java Stream的API来简化代码。
* 2. 使用Stream.iterate创建一个流,在流中根据token类型执行相应的操作。
*/
import java.util.stream.Stream;
import java.util.Stack;
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
Stream.of(tokens).forEach(token -> {
switch (token) {
case "+":
stack.push(stack.pop() + stack.pop());
break;
case "-":
int b = stack.pop();
int a = stack.pop();
stack.push(a - b);
break;
case "*":
stack.push(stack.pop() * stack.pop());
break;
case "/":
int divisor = stack.pop();
int dividend = stack.pop();
stack.push(dividend / divisor);
break;
default:
stack.push(Integer.parseInt(token));
}
});
return stack.pop();
}
}
解释
方法:
这个题解使用了栈来求解逆波兰表达式。具体思路如下:遍历输入的 tokens 列表,如果当前元素是数字,就将其转换为整数后压入栈中;如果当前元素是运算符(+、-、*、/),就从栈顶弹出两个元素,按照该运算符进行计算,并将计算结果压回栈中。遍历完整个列表后,栈顶元素即为最终的计算结果。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
题解中提到的栈处理方法对于不同类型的运算符(+、-、*、/)是否有不同的处理细节,特别是在除法操作中如何确保向零截断?
▷🦆
在提到弹出两个元素进行计算时,为什么先弹出的是 num2 而后弹出的是 num1,这种顺序对计算结果有何影响?
▷🦆
如果输入的 tokens 数组为空或仅包含一个数字,这种情况下算法是否能正确处理,并且返回什么结果?
▷🦆
在处理负数运算时,题解是否考虑了负数与除法相结合时向零截断的特殊情况,例如计算 '-2' 和 '3' 除法的结果?
▷相关问题
基本计算器
给你一个字符串表达式 s
,请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval()
。
示例 1:
输入:s = "1 + 1" 输出:2
示例 2:
输入:s = " 2-1 + 2 " 输出:3
示例 3:
输入:s = "(1+(4+5+2)-3)+(6+8)" 输出:23
提示:
1 <= s.length <= 3 * 105
s
由数字、'+'
、'-'
、'('
、')'
、和' '
组成s
表示一个有效的表达式- '+' 不能用作一元运算(例如, "+1" 和
"+(2 + 3)"
无效) - '-' 可以用作一元运算(即 "-1" 和
"-(2 + 3)"
是有效的) - 输入中不存在两个连续的操作符
- 每个数字和运行的计算将适合于一个有符号的 32位 整数
给表达式添加运算符
给定一个仅包含数字 0-9
的字符串 num
和一个目标值整数 target
,在 num
的数字之间添加 二元 运算符(不是一元)+
、-
或 *
,返回 所有 能够得到 target
的表达式。
注意,返回表达式中的操作数 不应该 包含前导零。
示例 1:
输入: num =
"123", target = 6
输出: ["1+2+3", "1*2*3"]
解释: “1*2*3” 和 “1+2+3” 的值都是6。
示例 2:
输入: num =
"232", target = 8
输出: ["2*3+2", "2+3*2"]
解释: “2*3+2” 和 “2+3*2” 的值都是8。
示例 3:
输入: num =
"3456237490", target = 9191
输出: []
解释: 表达式 “3456237490” 无法得到 9191 。
提示:
1 <= num.length <= 10
num
仅含数字-231 <= target <= 231 - 1