Transform equation tree to coefficient matrix?

Question

Given some lineqr (in)equality, what is a simple algorithm to convert that into coefficient matrix form? So e.g given ((3(x+5)/(2(y-1)))<4(as tree, so operator order is clearly defined) how to efficiently transform that into 3x-8y<-23 or something equivalent? Any hints what algorithm to use?

Answer 1

Lets look at how you would do this by hand

((3(x+5)/(2(y-1)))<4              
3 (x+ 5) < ( 2 ( y - 1) ) * 4     Multiply by bottom note 1
3 x + 5 < 8 y - 8                 Expand
3 x - 8 y + 5 < -8                Take 8 y across
3 x - 8 y < -13                   Take 5 across

This only works if 2 (y-1) is positive, otherwise you would need to change the less than to greater than sign.

There are two basic strategies you can use.

1. Convert each individual node into a coefficient matrix and then perform mathematical operations on those matrices to get you final answer.

2. Simplify your expression and then convert it to a coefficient matrix.

Lets look an expression without division which complicates matters.

(3(x+5))*(2(y-1))<4  

And write or coefficient matrices as [3] for a constant 3. [x,0] for x, [2 y,0] for 2 y. Converting each leaf node to coefficients gives

([3]*([x,0]+[5]))*([2]*([y,0]-[1]))<[4]

Working up the tree

([3]*[x,5])*([2]*[y,-1])<[4]
[3 x,15]*[2 y,-2] < [4]
[6 x y,-6 x, 30 y, -30] < [4]
[6 x y,-6 x, 30 y, -34] < [0]

To actually implement this you need a class for a coefficient matrix, which has methods to perform each basic operation. Assume we know are answers are all going to be polynomials in x and y. Our class might be something like

class Polynomial {
    double data[][];
    int degX,degY;
    // Constructor from a constant
    Polynomial(double val) { 
        data = new double[1][1];
        data[0][0]=val;
        degX = degY = 0;
    }
    // Constructor from a variable
    Polynomial(String name) {
        if(name == "x") {
            data = new double[2][1];
            data[1][0]=1;
            degX=1; degY=0;
        } else if( name=="y") [
            data = new double[1][2];
            data[0][1]=1;
            degX=1; degY=0;
        }
    }

    // Add two polynomials
    Polynomial add(Polynomial A,Polynomial B) {
        int dX = max(A.degX,B.degX);
        int dY = max(A.degY,B.degY);
        double coeffs[][] = new double[dx+1][dy+1];
        for(int i=0;i<A.degX;++i)
            for(int j=0;j<A.degY;++j)
                coeffs[i][j] += A.data[i][j]; 
        for(int i=0;i<B.degX;++i)
            for(int j=0;j<B.degY;++j)
                coeffs[i][j] += B.data[i][j]; 
        return new Polynomial(coeffs,degX,degY);
    }

    // Multiply two polynomials
    Polynomial mul(Polynomial A,Polynomial B) {
        int dx = A.degX * B.degX;
        int dy = A.degY * B.degY;
        double coeffs[][] = new double[dx+1][dy+1];
        for(int i=0;i<A.degX;++i)
          for(int j=0;j<A.degY;++j)
            for(int k=0;k<B.degX;++k)
              for(int l=0;l<A.degY;++l)
                coeffs[i+k][j+l] = coeffs[i][j] * coeffs[k][l];
        return new Polynomial(coeffs,degX,degY);
    }
}

You then want a depth first recursive tree traversal routine

Polynomial walk(Node n) {
    if( isConstant(n) )
        return new Polynomial( n.value );
    if( isIdentifier(n) )
        return new Polynomial( n.name );
    if( node.op = "+" )
        return Polynomial.add( walk(n.left), walk(n.right) );
    if( node.op = "*" )
        return Polynomial.mul( walk(n.left), walk(n.right) );
}

Division makes things considerably harder.