给表达式添加运算符

难度:

标签:

题目描述

给定一个仅包含数字 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 仅含数字
-2³¹ <= target <= 2³¹ - 1

代码结果

运行时间: 363 ms, 内存: 16.4 MB

/*
题目思路：
1. 使用 Java Stream 来实现与 Java 解法类似的回溯法。
2. 通过构造所有可能的表达式并过滤出结果为 target 的表达式。
*/
 
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public class SolutionStream {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        IntStream.range(1, num.length()).forEach(i -> 
            IntStream.range(i, num.length()).forEach(j -> 
                IntStream.of('+', '-', '*').forEach(op -> {
                    String expr = num.substring(0, i) + (char)op + num.substring(i, j) + (char)op + num.substring(j);
                    try {
                        if (eval(expr) == target) {
                            result.add(expr);
                        }
                    } catch (Exception e) { /* ignore invalid expressions */ }
                })
            )
        );
        return result;
    }
    
    private long eval(String expr) throws Exception {
        Stack<Long> stack = new Stack<>();
        long num = 0;
        char sign = '+';
        for (int i = 0; i < expr.length(); i++) {
            char c = expr.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + c - '0';
            }
            if ((!Character.isDigit(c) && c != ' ') || i == expr.length() - 1) {
                if (sign == '+') stack.push(num);
                else if (sign == '-') stack.push(-num);
                else if (sign == '*') stack.push(stack.pop() * num);
                sign = c;
                num = 0;
            }
        }
        long result = 0;
        for (long n : stack) result += n;
        return result;
    }
}

解释

方法:

该题解使用回溯法，采用深度优先搜索的思路，递归地在数字字符串的每个位置尝试添加不同的运算符（+、- 或 *），生成所有可能的表达式，并在表达式结果等于目标值时加入结果列表。在递归过程中，通过维护当前的计算结果 res 和上一次乘法的值 mul，可以在添加新运算符时，根据上一次的操作符进行相应的计算。

时间复杂度:

O(4^n)

空间复杂度:

O(n) + O(4^n)

代码细节讲解

🦆

在`helper`函数中，`res - mul + mul * val`这个表达式的计算逻辑是什么意思，能否详细解释一下？

▷

在`helper`函数中，表达式`res - mul + mul * val`用于处理乘号`*`的运算。这里的逻辑是首先撤销上一次运算的结果，然后将上一次的结果与当前数字`val`进行乘法运算。例如，如果表达式是`a+b*c`，在递归中，当处理到`b`时，`res`是`a+b`，`mul`是`b`。接下来要处理`c`，我们首先从`res`中减去`mul`（即减去`b`），然后再加上`b*c`，这样更新的`res`就是`a+b*c`的结果。这种方法允许我们在不维护表达式的具体结构的情况下，正确地处理乘法运算的优先级。

🦆

如果输入的数字字符串`num`非常长，这种递归回溯方法的性能如何？是否有可能造成栈溢出或者超时？

▷

如果输入的数字字符串`num`非常长，递归回溯方法的执行时间和空间消耗将会显著增加，因为算法需要枚举所有可能的运算符插入方式，其时间复杂度大约为`O(3^n)`，其中`n`是数字的长度。这可能导致在极端情况下执行时间过长（超时）或递归调用层数过多而引起栈溢出。在实际应用中，通常需要对输入的长度或递归的深度有一定的限制，以防止这种情况发生。

🦆

题解中提到的‘如果当前数字为 0，且不是单独的 0，则不继续处理’，这种情况下如何处理数字例如'105'或者'205'？

▷

题解中的这个规则是为了防止数字以`0`开头，除非`0`是单独的一个数字。例如，`105`和`205`中的`0`并不单独，而是数字的一部分，因此可以正常处理。但是，如果数字如`010`或`005`，则应该避免生成以`0`开头的多位数。具体到`105`或`205`，算法将正常处理`1`和`2`，然后继续处理后面的数字，不会中断处理。

🦆

为什么在处理第一个数字时不需要添加运算符，直接递归处理下一个数字？这样的设计有什么特别的考虑吗？

▷

这样设计的原因是表达式的开始不能有运算符，第一个数字前面没有其他数字或运算符，因此直接将第一个数字作为开始的部分，并递归处理后续的数字和运算符。这不仅符合数学表达式的规则，也简化了逻辑处理，避免在表达式开始就处理不必要的运算符插入逻辑。

相关问题

逆波兰表达式求值

给你一个字符串数组 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 <= 10⁴
tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

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

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

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

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

基本计算器

给你一个字符串表达式 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 * 10⁵
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32位整数

基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-2³¹, 2³¹ - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "3+2*2"
输出：7

示例 2：

输入：s = " 3/2 "
输出：1

示例 3：

输入：s = " 3+5 / 2 "
输出：5

提示：

1 <= s.length <= 3 * 10⁵
s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 2³¹ - 1] 内
题目数据保证答案是一个 32-bit 整数

为运算表达式设计优先级

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10⁴ 。

示例 1：

输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2：

输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

提示：

1 <= expression.length <= 20
expression 由数字和算符 '+'、'-' 和 '*' 组成。
输入表达式中的所有整数值在范围 [0, 99]

目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

锯齿迭代器移动零