diff options
Diffstat (limited to 'lab1/src/main/scala/jsy/lab1/Lab1.scala')
-rw-r--r-- | lab1/src/main/scala/jsy/lab1/Lab1.scala | 115 |
1 files changed, 115 insertions, 0 deletions
diff --git a/lab1/src/main/scala/jsy/lab1/Lab1.scala b/lab1/src/main/scala/jsy/lab1/Lab1.scala new file mode 100644 index 0000000..d3a73b1 --- /dev/null +++ b/lab1/src/main/scala/jsy/lab1/Lab1.scala @@ -0,0 +1,115 @@ +package jsy.lab1 + +object Lab1 { + /* + * CSCI 3155: Lab 1 + * Jack Sangdahl + * 09 September 2024 + * + * Partner: N/A + * Collaborators: N/A + */ + + /* Example: Test-driven development of `plus` */ + + def plus(x: Int, y: Int): Int = x + y + + /* Exercises */ + + def repeat(s: String, n: Int): String = { + require(n >= 0) + if (n == 0) "" + else s + repeat(s, n - 1) + } + + def sqrtStep(c: Double, xn: Double): Double = { + val n = (xn * xn) - c + val d = 2 * xn + xn - (n / d) + } + + def sqrtN(c: Double, x0: Double, n: Int): Double = { + require(n >= 0 && c >= 0) + if (n == 0) x0 + else sqrtN(c, sqrtStep(c, x0), n - 1) + } + + def sqrtErr(c: Double, x0: Double, epsilon: Double): Double = { + require(epsilon > 0) + val next = sqrtStep(c, x0) + if (Math.abs((x0 * x0) - c) < epsilon) x0 + else sqrtErr(c, next, epsilon) + } + + def sqrt(c: Double): Double = { + require(c >= 0) + if (c == 0) 0 else sqrtErr(c, 1.0, 0.0001) + } + + /* Search Tree */ + + sealed abstract class Tree + case object Empty extends Tree + case class Node(l: Tree, d: Int, r: Tree) extends Tree + + def repOk(t: Tree): Boolean = { + def check(t: Tree, min: Int, max: Int): Boolean = t match { + case Empty => true + case Node(l, d, r) => + d >= min && d < max && check(l, min, d) && check(r, d, max) + } + check(t, Int.MinValue, Int.MaxValue) + } + + def insert(t: Tree, n: Int): Tree = t match { + case Empty => Node(Empty, n, Empty) + case Node(l, d, r) => + if (n < d) Node(insert(l, n), d, r) + else Node(l, d, insert(r, n)) + } + + def deleteMin(t: Tree): (Tree, Int) = { + require(t != Empty) + (t: @unchecked) match { + case Node(Empty, d, r) => (r, d) + case Node(l, d, r) => + val (l1, m) = deleteMin(l) + (Node(l1, d, r), m) + } + } + + def delete(t: Tree, n: Int): Tree = t match { + case Empty => Empty + case Node(l, d, r) => + if (n < d) Node(delete(l, n), d, r) + else if (n > d) Node(l, d, delete(r, n)) + else if (l == Empty) r + else if (r == Empty) l + else { + val (r1, min) = deleteMin(r) + Node(l, min, r1) + } + } + /* Evaluate the JavaScripty Calculator Language */ + + /* We import `jsy.lab1.ast._` so that we can make use of the Expr type defined + * there. Take a look at ast.scala to see what the Expr type looks like, as well + * some helper functions for defining values (`isValue`) and pretty-printing + * (`pretty`) that you are welcome to use. + */ + import jsy.lab1.ast._ + + def eval(e: Expr): Double = e match { + case N(n) => n + case Unary(Neg, e1) => -eval(e1) + case Binary(Plus, e1, e2) => eval(e1) + eval(e2) + case Binary(Minus, e1, e2) => eval(e1) - eval(e2) + case Binary(Times, e1, e2) => eval(e1) * eval(e2) + case Binary(Div, e1, e2) => eval(e1) / eval(e2) + } + + /* We also overload `eval` to take a String and parse it into an Expr and then + * evaluate it using your `eval` function defined above. + */ + def eval(e: String): Double = eval(Parser.parse(e)) +} |