Algabraic Equation Solver

{:deps
 {org.clojure/clojure {:mvn/version "1.10.0"}
  instaparse {:mvn/version "1.4.10"}}}
deps.edn
Extensible Data Notation

Adapted from the infix calculator in "The AWK Programming Language", Chapter 5, which all too conveniently uses a context-free grammar that we can pass right to Instaparse. All I've done here is expand it to support variables and implicit multiplication for equations.

(ns algae.core
  (:require [instaparse.core :as insta]))

(def equation
  (insta/parser
   "<equation> = left <'='> right
   left = expr+
   right = expr+
   <expr> = term | (expr '+' term) | (expr '-' term)
   <term> = factor | (term '*'? factor) | (term '/' factor)
   <factor> = number | variable | <'('> expr <')'>
   number = #'[0-9]+'
   variable = #'[A-Za-z]'"))
algae.core/equation

But wait... The Instaparse documentation already gave us a basic infix parser, and also demonstrates how to use insta/transform to evaluate expressions. But this grammar (from the AWK text:) "... captures not only the form of arithmetic expressions but also the precedences and associativities of the operators. For example, an expr is the sum or difference of terms, but a term is made up of factors, which assures that multiplication and division are dealt with before addition or subtraction."

We'll use some problems from Khan Academy:

Solve the equation.

First, here is our parse tree:

(equation "20=r+11")
List(2) (Vector(2), Vector(4))

What we want the solver to do (ultimately) is to analyze the tree and figure out which operation to perform. But first we'll just take this one as a given and make a function to solve it for . Since one side is a single number and the other is and a number, we just need to subtract the from the :

(defn left [s]
  (rest (first (equation s))))

(defn right [s]
  (rest (last (equation s))))

(defn solve [s]
  (let [left-num (Integer/parseInt (first (rest (first (left s)))))
        right-num (Integer/parseInt (last (last (right s))))
        right-var (last (first (right s)))]
    (str right-var " = " (- left-num right-num))))

(solve "20=r+11")
"r = 9"

Cool... but needs to be generalized, obviously. Working with these nested vectors seems really awkward the way I'm trying to do it. I feel like I'm missing something, but let's just do some more and see how it goes, see which patterns emerge.

See, this one is perfect because it just switches the order of the right terms. This forces us to write a function that will check that.

0.1s
Clojure
(defn left-num [s]
  (cond
    (= :number (first (first (left s))))
    (Integer/parseInt (last (first (left s))))
    (= :number (first (last (left s))))
    (Integer/parseInt (last (last (left s))))
    :else nil))

(defn right-num [s]
  (cond
    (= :number (first (first (right s))))
    (Integer/parseInt (last (first (right s))))
    (= :number (first (last (right s))))
    (Integer/parseInt (last (last (right s))))
    :else nil))

(defn left-var [s]
  (cond
    (= :variable (first (first (left s))))
    (last (first (left s)))
    (= :variable (first (last (left s))))
    (last (last (left s)))
    :else nil))

(defn right-var [s]
  (cond
    (= :variable (first (first (right s))))
    (last (first (right s)))
    (= :variable (first (last (right s))))
    (last (last (right s)))
    :else nil))

(left-num "27=15+n")
27

Cool, now we can solve it like this:

(defn solve [s]
    (str (right-var s) " = " (- (left-num s) (right-num s))))

(solve "27=15+n")
"n = 12"
(solve "24=y+19")
"y = 5"

(defn solve [s]
  (if (left-var s)
    (str (left-var s) " = " (- (right-num s) (left-num s)))
    (str (right-var s) " = " (- (left-num s) (right-num s)))))

(solve "p+12=30")
"p = 18"

OK now subtraction! Let's extract the minus sign to find out what operation to perform:

(defn operator [s]
  (if (= 3 (count (left s)))
    (second (left s))
    (second (right s))))

(operator "x-21=6")
"-"
(defn solve [s]
  (if (left-var s)
    (str (left-var s) " = "
         (if (= "-" (operator s))
           (+ (right-num s) (left-num s))
           (- (right-num s) (left-num s))))
    (str (right-var s) " = "
         (if (= "-" (operator s))
           (+ (left-num s) (right-num s))
           (- (left-num s) (right-num s))))))

(solve "x-21=6")
"x = 27"
(solve "19=14+k")
"k = 5"