arrays - JavaScript -- write a function that can solve a math expression (without eval)

Question

Ultimately I want to take this:

2x + 3 = 5

and solve for x, by first subtract 3 from both sides so 2x = 2, then divide both sides by 2 so x = 1. I was thinking a lot how one should go about making a function like this in JavaScript that can return an array of the steps done in order, including the result. Obviously "eval" wouldn't do anything for this, so seemingly one has to re-create equations.

I initially thought to first of all, ignore X, and just try to make a function that can solve simple equations, without eval or any built-in function.

I figured that the first step is to break up the terms using .split, but I was having some trouble with this, as I need to split for multiple symbols. For example, say I have the simple expression to evaluate: 3 - 6 * 3 / 9 + 5. So before we even get into order of operations, just splitting up each term (and categorizing them) is the hard part, which is the main concrete-question I have at this point.

I started simply splitting one after the other, but I was having some problems, and especially considering the order.

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");

Answer 1

While your problem doesn't require to construct, binary expression tree is a good way to brainstorm the logic to solve a math query.

So for the query 3 - 6 * 3 / 9 + 5, the representative binary expression tree is:

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

to solve above tree, you recursively solve from the leaf level up to the root.

Again, you don't need to construct a tree. It just helps us to see the logic of parsing here:

• Get the last minus or plus expression in query and solve left and right child of that expression.
• If no plus/minus, get the last times/division expression and solve left and right child
• If meet a number, return that number value.

Given above logic, here is an implementation:

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"));