3

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

As you can see, for each successive operator I need to map through each of he elements of the previous one to split it, and then I am left with an array of arrays etc...

So 1) how can I split up these terms more efficiently, without making a new variable for each one, and manually recursively mapping through each one? Seemingly I should just have some kind of dictionary of array keeping track of orders of operations (not considering parenthesis or exponents now): ["*","/","+","-"] -- and given that array, generate something similar to the last array in the above example ("dividers") which contains only constants, and somehow keep track of the which elements each of the stored arrays follows...

and 2) How can I solve the expression given the arrays of values?

I was just a little confused with the logic, I guess I need to work up from the last array and solve the constants one at a time, keeping track of which operator is the current one, but I'm not sure how exactly.

B''H Bi'ezras -- Boruch Hashem
  • 3,665
  • 3
  • 33
  • 83
  • Do you want to evaluate expression according to dmas rule or not? – Maheer Ali Apr 29 '19 at 04:12
  • @MaheerAli Well yes I want to follow the order of operations, is dmas, putting division before multiplication, essentially the same thing as multiplication before division? So either way, but I don't think there's any way to correctly solve it by doing the addition and subtraction first – B''H Bi'ezras -- Boruch Hashem Apr 29 '19 at 04:14
  • You might want to read through https://stackoverflow.com/questions/28256/equation-expression-parser-with-precedence and https://stackoverflow.com/questions/114586/smart-design-of-a-math-parser first. Math parser is not quite trivial, so you can consider using third party lib to solve. As for the second problem, you can construct a binary expression tree with `=` be the root, and move root from right to left while balancing values of left and right child. – blaz Apr 29 '19 at 04:28
  • @blaz I don't plan on using any third party libraries, the point is to make it from scratch, the basic idea is simply to split up the terms using .split, and solve by working backwards, but the only blockage I'm having is just how to do that neatly – B''H Bi'ezras -- Boruch Hashem Apr 29 '19 at 04:39

2 Answers2

4

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

Above is a solution for very simple query with only +, -, *, / (no parenthesis, e.g.). For solving a equation like your first example requires a lot more of work.

EDIT: add a parse function to return the tree.

blaz
  • 3,981
  • 22
  • 37
2

You can do that in following steps:

  • First of all use split() and split by the + and - which will occur after multiplication and division.
  • Then use map() on array and split() it again by * and /.
  • Now we have a function which will which will evaluate an array of numbers with operators to single number.
  • Pass the nested array to complete multiplication and division.
  • Then pass that result again to sovleSingle and perform addition and subtraction.

The function works same as eval as long as there are no brackets ().

Note: This doesnot matters the which occurs first among + and - or which occurs first among * and /. But *,/ should occur before +,-

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
Maheer Ali
  • 35,834
  • 5
  • 42
  • 73