Clojure Equation Solver (Part 2)
If you’re here from Part 1, read on. If not, what are you doing here?
In Part 1 of this awfully long post I converted an infix equation string into an abstract syntax tree. Now we can finally solve for :var. This can be accomplished with a recursive function as well, using a method known in this as Isolation (see section 3.1). The basic idea is that the single variable is “hidden” under multiple layers of composed operations, and an iteration of the function will remove a single layer of composition. For example:
3+4*x=19 4*x=19-3
--->
= =
+ 19 * -
3 * 4 x 19 3
4 x
Hopefully the above ASCII art makes it apparent, but by applying the inverse operations, the variable moves up one level. Eventually, the variable will rise to be the singular left child of the equation, at which point the right side of the equation can just be evaluated.
First things first- now that we have an actual tree, I’m going to set up some helper functions to make tree operations a bit more transparent:
(defn left
"gets the left child of tree"
[tree]
(if (list? tree)
(nth tree 1)
nil))
(defn right
"gets the right child of tree"
[tree]
(if (list? tree)
(nth tree 2)
nil))
Nothing really to explain there, most of it is just syntactical. The only thing possibly to note is that if the arg doesn’t have the corresponding child it just returns nil.
Next is a hasvar? function, which checks if the passed tree contains the :var node. It’s use will become clear later:
(defn hasvar?
"checks if the (sub)tree has the variable"
[tree]
(if (list? tree)
(or
(hasvar? (left tree))
(hasvar? (right tree))
false)
(= tree :var)))
Now the first thing to do is to move the variable to the left side of the equation (in correspondence with most of our middle school math educations). Since this only needs to be done once, I can afterwards recurse with the modified tree and a dummy argument (0 in this case). By only checking which side the variable is on when there’s no dummy argument, I can save myself from having to do an unnecessary O(n) depth first search each time I recurse.
(defn solvetree
"solve an equation in one variable given its ast"
([eqn] ; initial call
(if (hasvar? (right eqn)) ; if the right side of the equation has the variable
(solvetree (list (first eqn) (right eqn) (left eqn)) 0) ; switch the left and right subtrees
(solvetree eqn 0))) ; otherwise just call it again -- WITH the dummy
([eqn _] ; calling with the dummy arg, so it skips the above
...
Let’s get the simple out of the way– first, I can check if the left side is just :var. In that case, I can just return the evaluated right side.
([eqn _] ; guarantee that the variable is on the left side
(if (= (left eqn) :var) ; if the left child of the equal sign is :var
(evaltree (right eqn)) ; return the right tree
...
evaltree evaluates an abstract syntax tree consisting of only arithmetic.
(defn evaltree
"evaluates an expression given its ast"
[tree]
(if (list? tree)
((get-in opinfo [(first tree) :op]) (evaltree (left tree)) (evaltree (right tree)))
tree))
A pretty simple recursive depth first traversal. Here you can see that the operator is now being converted from its string form to its function form (via (get-in opinfo [(first tree) :op])).
As denoted above, if the left child of the equal sign isn’t :var, then it needs to remove a layer of operation. This is just case checking on case checking. First, I check to see if the variable is on the left or on the right of the left child of the equal sign. If the variable is on the left, then it’s a simple matter of applying the inverse operation and moving the other operand over. I can’t be bothered to write a better explanation so here’s another ASCII diagram:
x-4=5 x=5+4
--->
= =
- 5 x +
x 4 5 4
As you can see, because the :var is on the left of the minus operation, the tree transform is simply a matter of combining the right side of the equation under the inverse of the minus with the original right child of the minus. This is the same for all of the arithmetic operations, but is more important for subtraction and division, because the order of the operands matter for those operations. Note that the above is not possible if the :var were on the right side of the minus, since that would move it to the right side of the equation.
(if (hasvar? (left (left eqn))) ; if :var is on the left of the left of the equal sign
(recur (list "="
(left (left eqn)) ; move the :var branch up
(list (get-in opinfo [(first (left eqn)) :inv]) ; get the inverse operation
(right eqn)
(right (left eqn))))
0)
If you are skeptical, I can’t really tell you much more than to try some test cases out. After a while, it should become pretty intuitive that, for instance, x+5=9 goes to x=9-5, and x*4=10 goes to x=10/4, and so on.
Now, the cases where the :var is on the right side must be handled individually, I think. There are some patterns, but I found it easier to just hard code each of them:
(case (first (left eqn)) ; switch based on the operation
"+" (recur (list "=" ; eg. 4+x=5 -> x=5-4
(right (left eqn))
(list "-"
(right eqn)
(left (left eqn))))
0)
"-" (recur (list "=" ; eg. 4-x=5 -> x=4-5
(right (left eqn))
(list "-"
(left (left eqn))
(right eqn)))
0)
"*" (recur (list "=" ; eg. 4*x=5 -> x=5/4
(right (left eqn))
(list "/"
(right eqn)
(left (left eqn))))
0)
"/" (recur (list "=" ; eg. 4/x=5 -> x=4/5
(right (left eqn))
(list "/"
(left (left eqn))
(right eqn)))
0))))))
That’s the last of the program. Now I can solve simple algebraic equations of one variable when there’s only one instance of the variable! Go check out my lame demo page to try it for yourself. If you’ve read up to this point you’ll know not to push it too hard, because it is very feature light.
Thanks for reading! If I did a dumb or you want to scold me for being too verbose, send me an email or something.