# 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

#### Fastest Entity Framework Extensions

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*} //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
``````

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

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.

Prime Library

More Projects...