leetcode
leetcode 101 ~ 150
逆波兰表达式求值

逆波兰表达式求值

难度:

标签:

题目描述

给你一个字符串数组 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)

代码细节讲解

🦆
题解中提到的栈处理方法对于不同类型的运算符(+、-、*、/)是否有不同的处理细节,特别是在除法操作中如何确保向零截断?
在题解中,不同的运算符确实有不同的处理细节。对于加法、减法和乘法,直接按照普通的整数运算处理即可。而在处理除法时,Python中的除法`/`会得到浮点数结果,为了确保结果是整数并且向零截断,使用了`int()`函数将结果转换为整数。这种转换方式确保了即使在被除数和除数符号不同的情况下,也能正确地向零截断。例如,`int(-2/3)`会得到`0`,而`int(2/-3)`同样得到`0`。
🦆
在提到弹出两个元素进行计算时,为什么先弹出的是 num2 而后弹出的是 num1,这种顺序对计算结果有何影响?
在栈的操作中,最后进入的元素最先出来。因此,当从栈中连续弹出两个元素时,首先弹出的是最后压入的元素,作为 num2,其次弹出的是先压入的元素,作为 num1。这种顺序在执行运算时非常关键,尤其是在有方向性的运算(如减法和除法)中。例如,对于表达式 `3 4 -`,正确的计算顺序应该是`3 - 4`,这样如果顺序反了,结果也会不同。因此,保持 num1 和 num2 的这种弹出顺序对于保证正确的运算结果是必需的。
🦆
如果输入的 tokens 数组为空或仅包含一个数字,这种情况下算法是否能正确处理,并且返回什么结果?
根据题解的代码,如果输入的 tokens 数组为空,则由于没有任何元素去填充栈,最终在尝试返回 `stack[0]` 时会因为栈为空而产生错误。如果 tokens 数组仅包含一个数字,这个数字会被压入栈中,然后在程序结束时返回 `stack[0]`,也就是该数字。因此,在只有一个元素的情况下算法能正确返回该数字,但对于空数组则无法正确处理,理应在实际应用中增加对这种情况的检查。
🦆
在处理负数运算时,题解是否考虑了负数与除法相结合时向零截断的特殊情况,例如计算 '-2' 和 '3' 除法的结果?
题解中确实考虑了负数与除法操作相结合时向零截断的情况。通过使用 `int()` 函数来处理除法结果,确保了无论正负数如何组合,结果都会正确地向零截断。在 Python 中,`int()` 函数会将浮点数向零截断,确保了像 `-2 / 3` 这样的运算结果是 `0`。这种处理方式满足了逆波兰表达式求值的要求。

相关问题

基本计算器

给你一个字符串表达式 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