2
$\begingroup$

i am currently working on a school project that takes in a simple linear equation and has to return the value of x, the code i have transforms x + 3 = 3x - 2 into a binary tree format like so:

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

now that i have the expression in this format could someone please explain how can i obtain the value of x, any help is appreciated and if you have an alternative method that may make it easier i would love to hear it thank you

$\endgroup$
  • $\begingroup$ Interesting question (+1). I suspect that there might be a way to go from the parse tree to a solution (if one exists), but it's not obvious to me. For example, you need to ensure that both the left and right subtrees produce a linear expression. That would mean that the subtrees of any * node can't both be expressions involving $x$. Given these constraints, as I said, I suspect that you could manipulate the parse tree to get the solution, but I'll have to look at it later. For practical purposes, I'd just use @Yuval's idea. $\endgroup$ – Rick Decker Apr 7 '15 at 1:02
3
$\begingroup$

You don't really want to solve the equation using this representation. You want to convert it into a normal form such as $ax+b = 0$, from which you can read the solution. The first step would be to replace $P = Q$ with $P - Q = 0$. The second step would be to normalize $P - Q$ to some standard form, say a polynomial (or in you case, perhaps $ax+b$). One way to do this is to convert each subexpression into normal form recursively, using rules for handling leaves such as numerical constants and $x$, and mathematical operations such as $+,-,\times$.

$\endgroup$
  • $\begingroup$ thank you, i implemented your idea and it worked like a charm $\endgroup$ – Darksonic6811 Apr 7 '15 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.