Solving linear equations represented as a string

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?

Answer 1

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.