Simplifying expression trees

Question

I am trying to write a program that simplifies mathematical expressions.

I have already written a parser that converts a string to a binary tree. For example (1+2)*x will become

    *
   / \
  +   x
 / \
1   2

The idea I had of simplifying such trees is as follows: You store a set of trees and their simplified version For example

    *                       +
   / \                     / \
  a   +        and        *   *
     / \                 / \ / \
    b   c               a  b a  c

(Where a,b,c can be any subtree) Then, If I find a subtree that matches one of the stored trees, I will replace it with its simplified version.

If necessary I will repeat the process until the tree is fully simplified.

The problem with this approach is that it can't "combine like terms" in some cases. For example, if I try to store the tree:

      +                *
     / \      and     / \
    x   x            2   x

Then when I try to simplify the expression x+y+x, with the following tree:

    +
   / \
  x   +
     / \
    y   x  

It will not be simplified to 2x+y, because the subtree

      +     
     / \     
    x   x      

Is not contained in the tree, thus the tree will not be simplified.

I tried writing an explicit algorithm that combine like terms but there are too many cases to consider.

Can anyone please help me find a solution to this problem?

Answer 1

Here is one of the basic ideas which is used in computer algebra systems.

For operators like Plus (+) and Times (*) you can define attributes like Flat (associativity) and Orderless (commutativity). Also don't define Plus and Times as "binary" operators but as "multiple-argument" operators.

So an input like:

Plus(x,Plus(y,x))

in the first step can be transformed (flattened) because of the Flat attribute to

Plus(x,y,x)

in the next step it can be transformed (sorted) because of the Orderless attribute to

Plus(x,x,y)

In your "evaluation" step you can now go through the arguments and "simplify" the expression to:

Plus(Times(2,x),y)

This approach has the advantage that expressions which are "structural equal" are stored in the same "canonical form" and could for example easier compared for "object equality" in the used programming language.

Answer 2

We may consider polynomials

we get the '+'-reducer and '*'-reducer for two polynomes in X

Now in the tree, instead of considering either a scalar or x as node, we may consider an "irreducible" polynomial.

Then we apply the '*'-reducer if the node operator is * or '+'-reducer otherwise which both transform two irreducibles polynome as an new irreducible one.

e.g where P_a, P_b two polynomes and

P_a = {
  x0: 1 // term of degree 0 idem 1
  x1: 2 // 2x
  x3: 4 // 4x^3
}

and P_b = {x1: 3}

we get for sum: P_a + P_b = {x0: 1, x1: 5, x3: 4}

(so tree ['+', P_a, P_b] simplifies as {x: 0, x1: 5, x3: 4})

we get for multiplication: P_a * P_b = {x1: 3, x2: 6, x3: 12}

At the end of the day, we get an irreducible polynome in X.

We can write back that polynome as a binary tree (which is thus a simplified tree):

for each monome (in X^i), write its associated binary tree (which only contains * operator) e.g: 5x^3 => ['*', ['*', ['*', x, x], x], 5] then sum them e.g: 1 + x + x^2 => ['+', 1, ['*', x, 1], ['*', x, x]

Same idea (idem implementing '+'-reducer/'*'-reducer) can be applied with an expression having polynomes in X, Y or Z, or whatever (so in your case, x, y)

below an example of implementation (you may uncomment and pass the tests using nodejs)

// a, b are polynomes of form {monomialKey: scalar, monomialKey2, scalar2, ...}
// a monomial key is e.g x1y2z2
const add = (a, b) => {
  const out = Object.assign({}, a)
  Object.entries(b).forEach(([monomialKey, scalar]) => {
    out[monomialKey] = (out[monomialKey] || 0) + scalar
    if (out[monomialKey] === 0) {
      delete out[monomialKey]
    }
  })
  return out
}
// transforms x1y2z2 to {x: 1, y: 2, z: 2}
const parseKey = s => s.match(/[a-z]+\d+/g).reduce((o, kv) => {
  const [,varname,deg] = kv.match(/([a-z]+)(\d+)/)
  o[varname] = parseInt(deg)
  return o
}, {})
const writeKey = o => Object.entries(o).reduce((s, [varname, deg]) => s + varname+deg, '')

// simplify monomial, e.g x1y3*x1 => x2y3
const timesMonomialKey = (iA, iB) => {
  const a = parseKey(iA)
  const b = parseKey(iB)
  const out = {}
  ;[a,b].forEach(x => Object.entries(x).forEach(([varname, deg]) => {
    if (deg === 0) return
    out[varname] = (out[varname] || 0) + deg
  }))
  if (Object.keys(out).length === 0) return writeKey({ x: 0 })
  return writeKey(out)
}
// a, b both polynomes
const times = (a, b) => {
  const out = {}
  Object.entries(a).forEach(([monimalKeyA, sA]) => {
    Object.entries(b).forEach(([monimalKeyB, sB]) => {
      const key = timesMonomialKey(monimalKeyA, monimalKeyB)
      out[key] = (out[key] || 0) + sA * sB
      if (out[key] === 0) {
        delete out[key]
      }
    })
  })
  return out
}


const reduceTree = t => { // of the form [operator, left, right] or val
  if (!Array.isArray(t)) {
    return typeof(t) === 'string'
      ? { [writeKey({ [t]: 1 })]: 1 } // x => {x1: 1}
      : { [writeKey({ x: 0 })]: t }  // 5 => {x0: 5}
  }
  const [op, leftTree, rightTree] = t
  const left = reduceTree(leftTree)
  const right = reduceTree(rightTree)
  return op === '+' ? add(left, right) : times(left, right)
}
const writePolynomial = o => {
  const writeMonomial = ([key, s]) => {
    const a = parseKey(key)
    const factors = Object.entries(a).flatMap(([varname, deg]) => {
      return Array.from({length: deg}).fill(varname)
    }).concat(s !== 1 ? s : [])
    return factors.reduce((t, next) => ['*', t, next])
  }
  if (Object.keys(o).length === 0) return 0
  return Object.entries(o).map(writeMonomial).reduce((t, next) => ['+', t, next])
}
console.log(writePolynomial(reduceTree(['+', ['+', 'x', 'y'], 'x'])))
//const assert = require('assert')
//assert.deepEqual(parseKey('x0y2z3'), { x: 0, y: 2, z: 3 })
//assert.deepEqual(writeKey({ x: 0, y: 2, z: 3 }), 'x0y2z3')
//assert.deepEqual(timesMonomialKey('x1y2', 'x3z1'), 'x4y2z1')
//assert.deepEqual(timesMonomialKey('x0y0', 'z0'), 'x0')
//assert.deepEqual(timesMonomialKey('x0y0', 'z0x1'), 'x1')
//assert.deepEqual(add({x0: 3, x1: 2}, {x0: 4, x3: 5}), {x0: 7, x1: 2, x3: 5})
//assert.deepEqual(add({x0: 3, y1: 2}, {x0: 4, y2: 5}), {x0: 7, y1: 2, y2: 5})
//assert.deepEqual(add({x0: 1}, {x0: -1}), {})
//assert.deepEqual(times({x0: 3, x1: 2}, {x0: 4, x1: 5}), {x0: 12, x1: 23, x2: 10})
//assert.deepEqual(times(
//  {x1y0: 3, x1y1: 2},
//  {x1y0: 4, x1y1: 5}),
//  {x2: 12, x2y1: 23, x2y2: 10}
//)
//assert.deepEqual(reduceTree('x'), {x1: 1})
//assert.deepEqual(reduceTree(['*', 2, 'x']), {x1: 2})
//assert.deepEqual(reduceTree(['+', 2, 'x']), {x0: 2, x1: 1})
//assert.deepEqual(reduceTree(['+', 'x', ['+', 'y', 'x']]), {x1: 2, y1: 1})
//assert.deepEqual(writePolynomial({ x1y1:1, x1y2: 2}), ['+', ['*', 'x', 'y'], ['*', ['*', ['*', 'x', 'y'], 'y'], 2]])
//assert.deepEqual(writePolynomial(reduceTree(['*', ['*', 'x', 'y'], 0])), 0)
//assert.deepEqual(writePolynomial(reduceTree(['+', ['*', ['*', 'x', 'y'], 0], 2])), 2)
//
//// finally your example :)
//assert.deepEqual(writePolynomial(reduceTree(['+', ['+', 'x', 'y'], 'x'])), ['+', ['*', 'x', 2], 'y'])