Bobbi Towers / Jun 08 2019
Remix of Clojure by Nextjournal

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]'"))
0.3s
Clojure
Clojure
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")
0.1s
Clojure
Clojure
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")
0.1s
Clojure
Clojure
"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
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")
0.1s
Clojure
Clojure
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")
0.1s
Clojure
Clojure
"n = 12"
(solve "24=y+19")
0.1s
Clojure
Clojure
"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")
0.2s
Clojure
Clojure
"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")
0.1s
Clojure
Clojure
"-"
(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")
0.2s
Clojure
Clojure
"x = 27"
(solve "19=14+k")
0.1s
Clojure
Clojure
"k = 5"