JavaScript - напишите функцию, которая может решить математическое выражение (без eval)

Question

В конечном итоге я хочу взять это:

2x + 3 = 5

и вычислите для x, сначала вычтите 3 с обеих сторон так, чтобы 2x = 2, затем разделите обе стороны на 2, чтобы x = 1. Я много думал о том, как сделать такую ​​функцию в JavaScript, которая может возвращать массив шагов, выполненных по порядку, включая результат. Очевидно, что «eval» ничего для этого не сделает, поэтому, похоже, нужно заново создавать уравнения.

Сначала я подумал, прежде всего, игнорировать X и просто попытаться создать функцию, которая может решать простые уравнения, без eval или какой-либо встроенной функции.

Я подумал, что первый шаг - разбить термины с помощью .split, но у меня возникли некоторые проблемы с этим, так как мне нужно разделить для несколько символов. Например, скажем, у меня есть простое выражение для оценки: 3 - 6 * 3 / 9 + 5. Поэтому, прежде чем мы перейдем к порядку операций, просто разбить каждый термин (и классифицировать их) - это сложная часть, , которая является основным конкретным вопросом, который у меня есть на данный момент.

Я начал просто разбивать одну за другой, но у меня были некоторые проблемы, особенно учитывая порядок.

function solve(eq) {
    var minuses = eq.split("-"),
            pluses = minuses.map(x=> x.split("+")),
            timeses = pluses.map(x=>x.map(y=>y.split("*"))),
      dividers = timeses.map(x=>x.map(y=>y.map(z=>z.split("/"))));
            console.log(minuses, pluses, timeses, dividers);
}

solve("3 - 6 * 3 / 9 + 5");

Как видите, для каждого последующего оператора мне нужно отобразить каждый из элементов предыдущего, чтобы разделить его, а затем у меня остается массив массивов и т. Д. *

Итак 1) как я могу более эффективно разделить эти термины , не создавая новую переменную для каждого, и вручную рекурсивно отображая каждое из них? Похоже, у меня просто должен быть какой-то словарь массива, отслеживающий порядок операций (без учета скобок или показателей): ["*","/","+","-"] - и, учитывая этот массив, сгенерировать что-то похожее на последний массив в приведенном выше примере («делители») ") который содержит только константы и каким-то образом отслеживает, за какими элементами следует каждый из хранимых массивов ...

и 2) Как мне решить выражение для массивов значений?

Я просто немного запутался с логикой, наверное, мне нужно поработать с последним массивом и решать константы по одному, отслеживая, какой оператор является текущим, но я не уверен, как точно.

Answer 1

Вы можете сделать это в следующих шагах:

• Прежде всего используйте split() и разделите на + и -, что произойдет после умножения и деления.
• Затем используйте map() для массива и split() снова для * и /.
• Теперь у нас есть функция, которая будет оценивать массив чисел с операторами в одно число.
• Передайте вложенный массив для завершения умножения и деления.
• Затем передайте этот результат снова sovleSingle и выполните сложение и вычитание.

Функция работает так же, как и eval, если нет скобок ().

Примечание : Это не имеет значения, которое встречается первым среди + и - или первым - среди * и /. Но *,/ должно произойти до +,-

function solveSingle(arr){
  arr = arr.slice();
  while(arr.length-1){
    if(arr[1] === '*') arr[0] = arr[0] * arr[2]
    if(arr[1] === '-') arr[0] = arr[0] - arr[2]
    if(arr[1] === '+') arr[0] = +arr[0] + (+arr[2])
    if(arr[1] === '/') arr[0] = arr[0] / arr[2]
    arr.splice(1,1);
    arr.splice(1,1);
  }
  return arr[0];
}

function solve(eq) {
  let res = eq.split(/(\+|-)/g).map(x => x.trim().split(/(\*|\/)/g).map(a => a.trim()));
  res = res.map(x => solveSingle(x)); //evaluating nested * and  / operations.
   
  return solveSingle(res) //at last evaluating + and -
  
  
}

console.log(solve("3 - 6 * 3 / 9 + 5")); //6
console.log(eval("3 - 6 * 3 / 9 + 5")) //6

Answer 2

В то время как ваша задача не требует построения, дерево двоичных выражений - хороший способ провести мозговой штурм в логике для решения математического запроса.

Так что для запроса 3 - 6 * 3 / 9 + 5,репрезентативное дерево двоичных выражений:

plus
  |_minus
  | |_3
  | |_divide
  |   |_times
  |   | |_3
  |   | |_6
  |   |_9
  |_5

для решения вышеупомянутого дерева вы рекурсивно решаете от уровня листа до корня.

Опять же, вам не нужно строить дерево,Это просто помогает нам увидеть логику синтаксического анализа здесь:

• Получить последний минус или плюс выражение в запросе и решить левый и правый дочерний элемент этого выражения.
• Если нет плюса /минус, получить последнее выражение умножения / деления и решить левый и правый дочерний элемент
• Если встретить число, вернуть это числовое значение.

Приведенная выше логика, вот реализация:

function solve(str) {
  var expressionIndex = Math.max(str.lastIndexOf("-"), str.lastIndexOf("+"));
  if (expressionIndex === -1) {
    expressionIndex = Math.max(str.lastIndexOf("*"), str.lastIndexOf("/"));
  }
  if (expressionIndex === -1) {
    var num = Number.parseInt(str.trim());
    if (isNaN(num)) {
      throw Exception("not a valid number");
    } else {
      return num;
    }
  } else {
    var leftVal = solve(str.substring(0, expressionIndex).trim());
    var rightVal = solve(str.substring(expressionIndex + 1).trim());
    switch (str[expressionIndex]) {
      case "+":
        return leftVal + rightVal;
      case "-":
        return leftVal - rightVal;
      case "*":
        return leftVal * rightVal;
      case "/":
        return leftVal / rightVal;
    }
  }
}

function parse(str) {
  var expressionIndex = Math.max(str.lastIndexOf("-"), str.lastIndexOf("+"));
  if (expressionIndex === -1) {
    expressionIndex = Math.max(str.lastIndexOf("*"), str.lastIndexOf("/"));
  }
  if (expressionIndex === -1) {
    var num = Number.parseInt(str.trim());
    if (isNaN(num)) {
      throw Exception("not a valid number");
    } else {
      return { type: "number", value: num };
    }
  } else {
    var leftNode = parse(str.substring(0, expressionIndex).trim());
    var rightNode = parse(str.substring(expressionIndex + 1).trim());
    return {
      type: "expression",
      value: str[expressionIndex],
      left: leftNode,
      right: rightNode
    };
  }
}

console.log(solve("3 - 6 * 3 / 9 + 5"));
console.log(parse("3 - 6 * 3 / 9 + 5"));

Выше приведено решение для очень простого запроса только с +, -, *, / (без скобок, например).Для решения уравнения, подобного вашему первому примеру, требуется гораздо больше работы.

РЕДАКТИРОВАТЬ : добавить функцию разбора для возврата дерева.