Calculate values with order of operations

This is one of those recommended exercises. On the surface it seems a piece of cake, but bodmas was a bit of a gotcha

Two attempts here.

The first uses regular expressions (in order) to globally match squares/square-roots, multiplication/division, and addition/subtraction.

For each operation the string uses string.replace to replace the matches with the calculated values returned from calcOperation.

const operators = {
  sqr: x => x * x,
  sqrt: x => Math.sqrt(x),
  '*': (x, y) => x * y,
  '/': (x, y) => x / y,
  '+': (x, y) => x + y,
  '-': (x, y) => x - y
}

const float = /-?\d+(?:\.\d+)?/.source

const groupExpressions = [
  new RegExp(float + 'sqrt?', 'g'), /* power/root */
  new RegExp(float + '(?:[*/]' + float + ')+', 'g'), /* multiply/divide */
  new RegExp(float + '(?:[-+]' + float + ')+', 'g') /* addition/subtraction */
]

function arrayFromExpr (expression) {
  return expression.match(/(-?\d+(?:\.\d+)?|sqrt?|[*/+-])/g)
}

function calcOperation (expression) {
  const parts = arrayFromExpr(expression)

  return parts.reduce((stored, part, i, partsArray) => {
    const operator = operators[part]

    return (operator)
      ? operator(parseFloat(stored), parseFloat(partsArray[i + 1]))
      : stored
  })
}

function calculate (expression) {
  return groupExpressions.reduce(
    (result, regEx) => result.replace(regEx, match => calcOperation(match)), expression
  )
}

test

console.log('-5+2*3sqr*4 =', calculate('-5+2*3sqr*4')) // -5+2*3sqr*4 = 67
console.log('5+2.5*4/2 =', calculate('5+2.5*4/2')) // 6+2.5*4/2 = 10

The second attempt I wanted to take a bit of the regular expression malarkey out of the equation.

This time the 6 operators are looped through one by one from square to subtraction.

For each iteration the whole expression is passed to calcOperation, along with the operator e.g. sqr : x => x * x and the expression with substituted values is returned.

const operators = [
  ['sqr', x => x * x],
  ['sqrt', x => Math.sqrt(x)],
  ['*', (x, y) => x * y],
  ['/', (x, y) => x / y],
  ['+', (x, y) => x + y],
  ['-', (x, y) => x - y]
]

/**
 * @param expression e.g. '5*4sqr'
 * @returns expression as an array e.g. ['5','*','4','sqr']
 */
function arrayFromExpr (expression) {
  return expression.match(/(-?\d+(?:\.\d+)?|sqrt?|[*/+-])/g)
}

/**
 * @param expression e.g. '5*4sqr'
 * @param operation e.g. {sqr: x => x * x}
 * @returns expression with substituted values e.g. '5*16'
 */
function calcOperation (expression, operation) {
  const expr = arrayFromExpr(expression)
  const result = []

  while (expr.length) {
    const part = expr.shift()
    const operator = operation[part]
    const prev = result.length - 1

    if (operator) {
      /* first check the arrity of the operator e.g. *(x,y) or sqr(x) */
      result[prev] = (operator.length === 2)
        ? operator(parseFloat(result[prev]), parseFloat(expr.shift()))
        : operator(parseFloat(result[prev]))
    } else result.push(part)
  }
  return result.join('')
}

/**
 * Loops through the operators in order of operation
 * substituting parts of the expression that match the operation
 * with a calculated value.
 * @param expression e.g. -5+2*3sqr*4
 * @returns final calculated value e.g. 67
 */
function calculate (expression) {
  return operators.reduce(
    (result, [operator, fn]) => calcOperation(result, { [operator]: fn }), expression
  )
}

Same test

console.log('-5+2*3sqr*4 =', calculate('-5+2*3sqr*4')) // -5+2*3sqr*4 = 67
console.log('5+2.5*4/2 =', calculate('5+2.5*4/2')) // 6+2.5*4/2 = 10

I am sure there are glaring flaws. I am also undecided as to which is the better approach and what refactoring could be done.

For instance initially operators was an object in the second attempt

operators = {
  sqr: x => x * x,
  sqrt: x => Math.sqrt(x)
  ...
}

I would have preferred that to using a map like array, unfortunately I need the predictable ordering of an iterable array.

Confess brains are a bit frazzled so any feedback would be appreciated:)

The next stage I am considering is to add brackets into the equation.

2 Likes

I think that would make very well for a recursive approach; here’s what I came up with, just split()ing the expression by the operators (in reverse order of precedence) to avoid regular expressions altogether:

const operators = {
  '^': (x, y) => x ** y,
  '/': (x, y) => x / y,
  '*': (x, y) => x * y,
  '-': (x, y) => x - y,
  '+': (x, y) => x + y
}

const mapping = Object
  .entries(operators)
  .reverse()

const calculate = (
  expression,
  [current, ...remaining] = mapping
) => {
  if (!current) {
    return Number(expression)
  }

  const [operator, fn] = current
  const terms = expression.trim().split(operator)

  return terms.map(term => calculate(term, remaining)).reduce(fn)
}

Seems to work as expected:

const assertCalculation = expression => {
  const calculated = calculate(expression)
  // eslint-disable-next-line no-eval
  const evaluated = eval(expression.replace('^', '**'))

  if (calculated !== evaluated) {
    throw Error(`Calculated ${calculated} from "${expression}", expected ${evaluated}`)
  }
}

assertCalculation('1')
assertCalculation('1 + 2 - 3')
assertCalculation('1 - 2 - 3')
assertCalculation('1 + 2 * 4 - 3 * 7 + 1')
assertCalculation('1 + 2 - 3 ^ 7 / 5 - 7')

Granted, this only works for binary operators right now. Thanks for the nice post anyway, exactly the right kind of brain twister for a rainy Saturday. :-)

1 Like

Very clever m3g4p0p. Still breaking things down and trying to wrap my head around your code

It’s coming to mind, that much like a recursive factorial the operations are processed starting from the base condition (FILO?), hence the need to reverse the operators. Is that right?

Thanks a lot :+1:

1 Like

You have to be careful there, for you can’t do all of the multiplication first before doing the division, or you can end up with the wrong answers.

Multiplication and division are performed in the order that they appear from left to right.

Yes I suppose you might call that FILO… I am first splitting the initial expression by the operator with the lowest precedence, since due to the recursion, this is the operator that is going to get applied last; then the resulting parts are split by the operator with the next lowest precedence etc., until eventually I only got numbers. Then the algorithm unfolds the recursion by applying the operators in the correct order of precedence; for example, with some added logging:

calculate('1 + 2 * 3 - 4 / 5 + 6 - 7 / 8 * 9')
// ->
split { level: 1, operator: '+', terms: [ '1 ', ' 2 * 3 - 4 / 5 ', ' 6 - 7 / 8 * 9' ] }
apply { level: 1, term: '1 ', result: 1 }
split { level: 2, operator: '-', terms: [ '2 * 3 ', ' 4 / 5' ] }
split { level: 3, operator: '*', terms: [ '2 ', ' 3' ] }
apply { level: 3, term: '2 ', result: 2 }
apply { level: 3, term: ' 3', result: 3 }
apply { level: 2, term: '2 * 3 ', result: 6 }
split { level: 4, operator: '/', terms: [ '4 ', ' 5' ] }
apply { level: 4, term: '4 ', result: 4 }
apply { level: 4, term: ' 5', result: 5 }
apply { level: 2, term: ' 4 / 5', result: 0.8 }
apply { level: 1, term: ' 2 * 3 - 4 / 5 ', result: 5.2 }
split { level: 2, operator: '-', terms: [ '6 ', ' 7 / 8 * 9' ] }
apply { level: 2, term: '6 ', result: 6 }
split { level: 3, operator: '*', terms: [ '7 / 8 ', ' 9' ] }
split { level: 4, operator: '/', terms: [ '7 ', ' 8' ] }
apply { level: 4, term: '7 ', result: 7 }
apply { level: 4, term: ' 8', result: 8 }
apply { level: 3, term: '7 / 8 ', result: 0.875 }
apply { level: 3, term: ' 9', result: 9 }
apply { level: 2, term: ' 7 / 8 * 9', result: 7.875 }
apply { level: 1, term: ' 6 - 7 / 8 * 9', result: -1.875 }

If I’m not mistaken, this won’t be a problem if you apply non-associative operators first though; i.e. subtraction before addition and division before multiplication.

1 Like

There are plenty of math puzzles that rely on that misunderstanding. When multiplication and division are not done in sequence as they occur along the equation, mistakes can and do occur.

1 Like

Hm okay, thanks for pointing that out. Do you have an example though so I can make my tests fail?

Here’s a good article about it.

Doesn’t the article actually say that it’s perfectly valid not to perform those operations in sequence? On the contrary:

The bottom line is that “order of operations” conventions are not universal truths in the same way that the sum of 2 and 2 is always 4.

Anyway I have yet to find an example there that would not pass my test; in the meanwhile,

calculate(expression) === eval(expression)

is good enough for me.