Solving linear equations represented as a string

algorithm expression-trees

Question

I'm given a string 2*x + 5 - (3*x-2)=x + 5 and I need to solve for x. My thought process is that I'd convert it to an expression tree, something like,

          =
        /  \
       -    +
      /\    /\
     +  -   x  5
    /\  /\ 
   *  5 * 2
  /\   /\
 2  x  3 x

But how do I actually reduce the tree from here? Any other ideas?

1
10
1/10/2014 8:05:05 AM

Accepted Answer

You have to reduce it using axioms from algebra

a * (b + c) -> (a * b) + (a * c)

This is done by checking the types of each node in the pass tree. Once the thing is fully expanded into terms, you can then check they are actually linear, etc.

The values in the tree will be either variables or numbers. It isn't very neat to represent these as classes inheriting from some AbstractTreeNode class however, because cplusplus doesn't have multiple dispatch. So it is better to do it the 'c' way.

enum NodeType {
    Number,
    Variable,
    Addition //to represent the + and *
}

struct Node {
    NodeType type;
    //union {char*,  int, Node*[2]} //psuedo code, but you need
    //something kind of like this for the 
    //variable name ("x") and numerical value
    //and the children
}

Now you can query they types of a node and its children using switch case.

As I said earlier - c++ idiomatic code would use virtual functions but lack the necessary multiple dispatch to solve this cleanly. (You would need to store the type anyway)

Then you group terms, etc and solve the equation.

You can have rules to normalise the tree, for example

constant + variable -> variable + constant

Would put x always on the left of a term. Then x * 2 + x * 4 could be simplified more easily

var * constant + var * constant -> (sum of constants) * var

In your example...

First, simplify the '=' by moving the terms (as per the rule above)

The right hand side will be -1 * (x + 5), becoming -1 * x + -1 * 5. The left hand side will be harder - consider replacing a - b with a + -1 * b.

Eventually,

2x + 5 + -3x + 2 + -x + -5 = 0

Then you can group terms ever which way you want. (By scanning along, etc)

(2 + -3 + -1) x + 5 + 2 + -5 = 0

Sum them up and when you have mx + c, solve it.

5
1/10/2014 8:04:55 AM

Popular Answer

Assuming the equation can reduce to f(x) = 0, and f(x) = a * x + b.

You can transform all the leaves in expression tree to f(x), for example : 2 -> 0 * x + 2, 3 * x -> 3 * x + 0, then you can do arithmetic operations of f(x) in expression tree. finally solve the equation f(x) = 0.

If the function is much more complicated than polynomial, you can do a binary search on x, and using the expression tree to calculate the left and right side of equation.



Related Questions





Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow