给表达式添加运算符

[louzhedong]

习题

出处 LeetCode 算法第282题

给定一个仅包含数字 0-9 的字符串和一个目标值，在数字之间添加二元运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。

示例 1:

输入: num = "123", target = 6
输出: ["1+2+3", "123"]
示例 2:

输入: num = "232", target = 8
输出: ["23+2", "2+32"]
示例 3:

输入: num = "105", target = 5
输出: ["1*0+5","10-5"]
示例 4:

输入: num = "00", target = 0
输出: ["0+0", "0-0", "0*0"]
示例 5:

输入: num = "3456237490", target = 9191
输出: []

思路

整体思路是回溯法，学艺不精，暂时只能做到所有数字之间都有运算符，无法处理类似"10-5"这种。🤣

解答

/**
 * @param {string} num
 * @param {number} target
 * @return {string[]}
 */
var addOperators = function (num, target) {
  var result = [];
  var numLength = num.length;
  var operateStr = "";
  return buildStr(operateStr, numLength - 1, result, num, target);
};

var buildStr = function (operateStr, length, result, num, target) {
  var operateMap = {
    0: "+",
    1: '-',
    2: "*",
  }
  if (operateStr.length < length) {
    for (var i = 0; i < 3; i++) {
      var temp = operateStr + operateMap[i];
      buildStr(temp, length, result, num, target);
    }
  } else {
    var obj = ifSatisfy(num, operateStr, target);
    if (obj.equal) {
      result.push(obj.str);
    }
  }

  return result;
}

var ifSatisfy = function (num, operateStr, target) {
  var computeStack = []; // 用来存放数字结果的堆栈
  var operateExpectMultipleArray = [];  // 用来存放除乘法之外的运算符
  var operateArray = [];
  for (var i = 0; i < operateStr.length; i++) {
    operateArray.push(num[i]);
    operateArray.push(operateStr[i]);
  }
  operateArray.push(num[num.length - 1]);


  for (var i = 0; i < operateArray.length; i++) {
    if (operateArray[i] == '*') {
      var before = computeStack.pop();
      var multiple = before * operateArray[i + 1];
      computeStack.push(multiple);
      i++;
    } else if (operateArray[i] == '+' || operateArray[i] == '-') {
      operateExpectMultipleArray.push(operateArray[i]);
    } else {
      computeStack.push(operateArray[i]);
    }
  }

  var result = Number(computeStack[0]);
  for (var i = 1; i < computeStack.length; i++) {
    if (operateExpectMultipleArray[i - 1] == '-') {
      result -= Number(computeStack[i]);
    } else {
      result += Number(computeStack[i]);
    }
  }

  if (result == target) {
    return {
      equal: true,
      str: operateArray.join("")
    }
  } else {
    return {
      equal: false
    }
  }
}