Support implicit multiplication operator

[silentmatt]

Consider adding support for an "implied multiplication" operator.

For example, these would be equivalent:

4x + 1 = 4*x + 1
a x + b = a*x + b

[Itangalo]

+1 on this feature request!

[Itangalo]

Another example: 2(a+b) = 2*(a+b)

A possible difficulty with implicit multiplications is if you have multi-character variables: Parser.parse("ab + 1").simplify({ab : -1, a : 5, b : 2}); // Should this be 0 or 11?

[Itangalo]

Here's one way of attacking implicit multiplication:

/**
 * Processes an expression string to make implicit multiplications explicit.
 *
 * @var expressionString
 *   A string with a complex expression, for example '2sin(x^xy)(x-y)+2(3+y)'
 * @var variables
 *   An array with the variables used in the expression, for example ['x', 'y']
 */
function preParseExpression(expressionString, variables) {
  var variables = variables.join('');

  // Build an object with replacement rules. (The order matters!)
  var re = {};
  // Turns 'x^xy' into 'x^(x*y)'.
  re.parenthesizeVariables = {
    expr : new RegExp('([0-9' + variables + ']+)([' + variables + ']+)'),
    repl : '($1*$2)',
  };
  // Turns '2(3+y)' into '2*(3+y)'.
  re.parenthesisCoefficients = {
    expr : /(\d+)([(])/i,
    repl : '$1*$2'
  };
  // Turns '(x^xy)(x-y)' into '(x^xy)*(x-y)'.
  re.parenthesisMultiplication = {
    expr : /([)])([(])/,
    repl : '$1*$2',
  };
  // Turns '2sin' into '2*sin'.
  re.functionCoefficients = {
    expr : /(\d+)([a-z]+)/i,
    repl : '$1*$2',
  };

  // Apply the replacement rules.
  for (var i in re) {
    while (expressionString.replace(re[i].expr, re[i].repl) != expressionString) {
      expressionString = expressionString.replace(re[i].expr, re[i].repl);
    }
  }

  return expressionString;
}

The function above has some drawbacks:

• You need to have a list of variables.
• If you have a variable 'i' and 'n', it will parse sin(3) to s_i_n*(3).
• If you have one variable x, one variable y and one variable xy, each occurance of of 'xy' will be split into 'x*y'.
• In general, I think the method above won't work very well with multi-character variables.

I think the second drawback can be helped, by someone who didn't spend the last few hours on trying to learn RegExp (like I did). I don't think the first drawback can be helped. Maybe if you compare against the list of functions known to Parser. The third drawback is not something that can be helped by code – it is inherent in how we use mathematical language. The fourth drawback could probably be helped, but would require a considerate amount of thinking. Having a solution for single-character variables seemed like a good start.

[Itangalo]

The code suggested above has problem with parsing negative terms.

I'm currently struggling with a replacement algorithm that can parse both x-2y and x/-2y properly. I'll post again if I find a better solution.

[Itangalo]

Ok, this seems to work. I have a feeling that it would be good to have some tests on this.

    var re = {};
    // Turns '2sin(x)' into '2*sin(x)'.
    re.letterCoefficients = {
      expr : /(\d)([a-z])/i,
      repl : '($1*$2)',
    };
    // Turns '2/xy' into '2/(x*y)'.
    re.parenthesizeVariableSequences = {
      expr : new RegExp('([' + variables + ']+)([' + variables + ']+)'),
      repl : '($1*$2)',
    };
    // Turns '2(x+5)' into '2*(x+5)'.
    re.parenthesisCoefficients = {
      expr : /(\d+)([(])/i,
      repl : '$1*$2'
    };
    // Turns '(x+1)(x+2)' into '(x+1)*(x+2)'.
    re.parenthesisMultiplication = {
      expr : /([)])([(])/,
      repl : '$1*$2',
    };
    // Resolves remaining negative signs: 'x^(-(2*y))' to x^((-1)*2*y)
    re.negativeSign = {
      expr : new RegExp('([^0-9a-z(])[-]+([(])'),
      repl : '$1((-1)*',
    };

[Itangalo]

No, there are still problems. Parsing expressions like 2x^2x requires that the algorithm takes order of operations into account – in the second case 2x should be interpreted as (2*x), but in the first case it should be 2*x (no parenthesis).

I start to think that this can't be done properly through pre-parsing the expression.

[silentmatt]

Thanks for the work you've put into this. I'll play around with it and see if I can come up with a solution to the problems. I'm not strongly opposed to only supporting single-character variables for this. Or maybe it could be an option. On May 8, 2014 4:29 PM, "Johan Falk" [email protected] wrote:

Ok, this seems to work. I have a feeling that it would be good to have some tests on this.

var re = {};
// Turns '2sin(x)' into '2*sin(x)'.
re.letterCoefficients = {
  expr : /(\d)([a-z])/i,
  repl : '($1*$2)',
};
// Turns '2/xy' into '2/(x*y)'.
re.parenthesizeVariableSequences = {
  expr : new RegExp('([' + variables + ']+)([' + variables + ']+)'),
  repl : '($1*$2)',
};
// Turns '2(x+5)' into '2*(x+5)'.
re.parenthesisCoefficients = {
  expr : /(\d+)([(])/i,
  repl : '$1*$2'
};
// Turns '(x+1)(x+2)' into '(x+1)*(x+2)'.
re.parenthesisMultiplication = {
  expr : /([)])([(])/,
  repl : '$1*$2',
};
// Resolves remaining negative signs: 'x^(-(2*y))' to x^((-1)*2*y)
re.negativeSign = {
  expr : new RegExp('([^0-9a-z(])[-]+([(])'),
  repl : '$1((-1)*',
};

— Reply to this email directly or view it on GitHubhttps://github.com/silentmatt/js-expression-eval/issues/1#issuecomment-42602174 .

[Itangalo]

I did some more reading, and it seems very difficult to parse 2x^2x into 2*x^(2*x) using generic rules. Most parsers accepting implicit multiplication treat it as 2*x^2*x – so I think that would be an acceptable way to go.

[Itangalo]

Hi again. I've done some more reading and testing, and have found a way to handle implicit multiplication that works better than the previous example: It introduces less parentheses, and it doesn't rely on an explicit list of variables to keep function name intact.

The algorithm is here presented as a pre-parsing function (since that's how I'm using it now):

// Makes implicit multiplication explicit.
function preParseExpression(expressionString) {
  expressionString = expressionString.toString();

  // Replace any function names in the expression with tokens, so they won't
  // confuse the replacements for implicit multiplication. (All the functions
  // and constants used by Parser can be found as properties in Parser.values.)
  var operators = Object.keys(Parser.values);
  // Sort the function names by length so we replace 'asin' before 'sin'. (This
  // avoids breaking function names.)
  operators.sort(function(a, b){
    return b.length - a.length;
  });

  // Build an object with replacement rules. (The order matters!)
  var re = {};

  // Replace function names with tokens. Include opening parenthesis of the function
  // argument, to avoid it being treated as an implicit multiplication.
  for (var i in operators) {
    re['op' + i] = {
      expr : new RegExp(operators[i] + '\\('),
      repl : '<' + i + '>',
    };
  }

  // Special case: The constant PI is understood by Parser, and should be replaced
  // to avoid treating the letters as an implicit multiplication.
  re.pi = {
    expr : /pi/i,
    repl : 'π',
  };

  // Replacements making implicit multiplication explicit:
  // a(x+1)(x+2) becomes a*(x+1)*(x+2). Most of this trick comes from
  // http://stackoverflow.com/questions/20912455/math-expression-parser
  // Cred to Reut Sharabani.
  re.implicit = {
    expr: /([0-9]+|[a-zπ\\)])(?=[a-zπ<\\(])/i,
    repl : '$1*',
  };
  // When implicit multiplications have been taken care of, we can return 'π' to 'PI'.
  re.piBack = {
    expr: /π/,
    repl : 'PI',
  };
  // Return any function names to the expression.
  for (var i in operators) {
    re['opBack' + i] = {
      expr : new RegExp('<' + i + '>'),
      repl : operators[i] + '(',
    };
  }

  // Apply the replacement rules.
  for (var i in re) {
    while (expressionString.replace(re[i].expr, re[i].repl) != expressionString) {
      expressionString = expressionString.replace(re[i].expr, re[i].repl);
    }
  }

  return expressionString;
}