--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/templates4/postfix.scala Wed Nov 28 17:13:40 2018 +0000
@@ -0,0 +1,102 @@
+// Shunting Yard Algorithm
+// by Edsger Dijkstra
+// ========================
+
+
+
+type Toks = List[String]
+
+// the operations in the simple version
+val ops = List("+", "-", "*", "/")
+
+// the precedences of the operators
+val precs = Map("+" -> 1,
+ "-" -> 1,
+ "*" -> 2,
+ "/" -> 2)
+
+// helper function for splitting strings into tokens
+def split(s: String) : Toks = s.split(" ").toList
+
+
+// (6) Implement below the shunting yard algorithm. The most
+// convenient way to this in Scala is to implement a recursive
+// function using pattern matching. The function takes some input
+// tokens as first argument. The second and third arguments represent
+// the stack and the output or the shunting yard algorithm.
+//
+// In the marking, you can assume the function is called only with
+// an empty stack and empty output list. You can also assume the
+// input are only properly formated (infix) arithmetic expressions
+// (for example all parentheses are well-nested, the input only contains
+// operators and numbers).
+
+// You can implement any helper function you need. I found it helpful
+// to implement auxiliary functions:
+
+def is_op(op: String) : Boolean = ops.contains(op)
+
+def prec(op1: String, op2: String) : Boolean = precs(op1) <= precs(op2)
+
+
+def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = (toks, st, out) match {
+ case (Nil, _, _) => out.reverse ::: st
+ case (num::in, st, out) if (num.forall(_.isDigit)) =>
+ syard(in, st, num :: out)
+ case (op1::in, op2::st, out) if (is_op(op1) && is_op(op2) && prec(op1, op2)) =>
+ syard(op1::in, st, op2 :: out)
+ case (op1::in, st, out) if (is_op(op1)) => syard(in, op1::st, out)
+ case ("("::in, st, out) => syard(in, "("::st, out)
+ case (")"::in, op2::st, out) =>
+ if (op2 == "(") syard(in, st, out) else syard(")"::in, st, op2 :: out)
+ case (in, st, out) => {
+ println(s"in: ${in} st: ${st} out: ${out.reverse}")
+ Nil
+ }
+}
+
+
+// test cases
+//syard(split("3 + 4 * ( 2 - 1 )")) // 3 4 2 1 - * +
+//syard(split("10 + 12 * 33")) // 10 12 33 * +
+//syard(split("( 5 + 7 ) * 2")) // 5 7 + 2 *
+//syard(split("5 + 7 / 2")) // 5 7 2 / +
+//syard(split("5 * 7 / 2")) // 5 7 * 2 /
+//syard(split("9 + 24 / ( 7 - 3 )")) // 9 24 7 3 - / +
+
+//syard(split("3 + 4 + 5")) // 3 4 + 5 +
+//syard(split("( ( 3 + 4 ) + 5 )")) // 3 4 + 5 +
+//syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + +
+//syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + +
+
+
+// (7) Implement a compute function that evaluates an input list
+// in postfix notation. This function takes an input list of tokens
+// and a stack as argument. The function should produce the
+// result in form of an integer using the stack. You can assume
+// this function will be only called with proper postfix expressions.
+
+def op_comp(s: String, n1: Int, n2: Int) = s match {
+ case "+" => n2 + n1
+ case "-" => n2 - n1
+ case "*" => n2 * n1
+ case "/" => n2 / n1
+}
+
+def compute(toks: Toks, st: List[Int] = Nil) : Int = (toks, st) match {
+ case (Nil, st) => st.head
+ case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st)
+ case (num::in, st) => compute(in, num.toInt::st)
+}
+
+// test cases
+// compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7
+// compute(syard(split("10 + 12 * 33"))) // 406
+// compute(syard(split("( 5 + 7 ) * 2"))) // 24
+// compute(syard(split("5 + 7 / 2"))) // 8
+// compute(syard(split("5 * 7 / 2"))) // 17
+// compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15
+
+
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/templates4/postfix2.scala Wed Nov 28 17:13:40 2018 +0000
@@ -0,0 +1,86 @@
+// Shunting Yard Algorithm
+// Edsger Dijkstra
+
+
+type Toks = List[String]
+
+def split(s: String) = s.split(" ").toList
+
+
+abstract class Assoc
+case object RA extends Assoc
+case object LA extends Assoc
+
+def assoc(s: String) : Assoc = s match {
+ case "^" => RA
+ case _ => LA
+}
+
+
+val precs = Map("+" -> 1,
+ "-" -> 1,
+ "*" -> 2,
+ "/" -> 2,
+ "^" -> 4)
+
+val ops = List("+", "-", "*", "/", "^")
+
+def is_op(op: String) : Boolean = ops.contains(op)
+
+def prec(op1: String, op2: String) : Boolean = assoc(op1) match {
+ case LA => precs(op1) <= precs(op2)
+ case RA => precs(op1) < precs(op2)
+}
+
+def syard(toks: Toks, st: Toks = Nil, rout: Toks = Nil) : Toks = (toks, st, rout) match {
+ case (Nil, _, _) => rout.reverse ::: st
+ case (num::in, st, rout) if (num.forall(_.isDigit)) =>
+ syard(in, st, num :: rout)
+ case (op1::in, op2::st, rout) if (is_op(op1) && is_op(op2) && prec(op1, op2)) =>
+ syard(op1::in, st, op2 :: rout)
+ case (op1::in, st, rout) if (is_op(op1)) => syard(in, op1::st, rout)
+ case ("("::in, st, rout) => syard(in, "("::st, rout)
+ case (")"::in, op2::st, rout) =>
+ if (op2 == "(") syard(in, st, rout) else syard(")"::in, st, op2 :: rout)
+ case (in, st, rout) => {
+ println(s"in: ${in} st: ${st} rout: ${rout.reverse}")
+ Nil
+ }
+}
+
+def op_comp(s: String, n1: Long, n2: Long) = s match {
+ case "+" => n2 + n1
+ case "-" => n2 - n1
+ case "*" => n2 * n1
+ case "/" => n2 / n1
+ case "^" => Math.pow(n2, n1).toLong
+}
+
+def compute(toks: Toks, st: List[Long] = Nil) : Long = (toks, st) match {
+ case (Nil, st) => st.head
+ case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st)
+ case (num::in, st) => compute(in, num.toInt::st)
+}
+
+
+
+
+compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7
+compute(syard(split("10 + 12 * 33"))) // 406
+compute(syard(split("( 5 + 7 ) * 2"))) // 24
+compute(syard(split("5 + 7 / 2"))) // 8
+compute(syard(split("5 * 7 / 2"))) // 17
+compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15
+
+compute(syard(split("4 ^ 3 ^ 2"))) // 262144
+compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144
+compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096
+
+
+syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / +
+compute(syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")))
+
+compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536
+
+
+def pow(n1: Long, n2: Long) = Math.pow(n1, n2).toLong
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/templates4/re.scala Wed Nov 28 17:13:40 2018 +0000
@@ -0,0 +1,123 @@
+// Part 1 about Regular Expression Matching
+//==========================================
+
+
+abstract class Rexp
+case object ZERO extends Rexp
+case object ONE extends Rexp
+case class CHAR(c: Char) extends Rexp
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence
+case class STAR(r: Rexp) extends Rexp // star
+
+
+// some convenience for typing in regular expressions
+
+import scala.language.implicitConversions
+import scala.language.reflectiveCalls
+
+def charlist2rexp(s: List[Char]): Rexp = s match {
+ case Nil => ONE
+ case c::Nil => CHAR(c)
+ case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
+
+implicit def RexpOps (r: Rexp) = new {
+ def | (s: Rexp) = ALT(r, s)
+ def % = STAR(r)
+ def ~ (s: Rexp) = SEQ(r, s)
+}
+
+implicit def stringOps (s: String) = new {
+ def | (r: Rexp) = ALT(s, r)
+ def | (r: String) = ALT(s, r)
+ def % = STAR(s)
+ def ~ (r: Rexp) = SEQ(s, r)
+ def ~ (r: String) = SEQ(s, r)
+}
+
+// (1) Complete the function nullable according to
+// the definition given in the coursework; this
+// function checks whether a regular expression
+// can match the empty string and Returns a boolean
+// accordingly.
+
+//def nullable (r: Rexp) : Boolean = ...
+
+
+// (2) Complete the function der according to
+// the definition given in the coursework; this
+// function calculates the derivative of a
+// regular expression w.r.t. a character.
+
+//def der (c: Char, r: Rexp) : Rexp = ...
+
+
+// (3) Complete the simp function according to
+// the specification given in the coursework; this
+// function simplifies a regular expression from
+// the inside out, like you would simplify arithmetic
+// expressions; however it does not simplify inside
+// STAR-regular expressions.
+
+//def simp(r: Rexp) : Rexp = ...
+
+
+// (4) Complete the two functions below; the first
+// calculates the derivative w.r.t. a string; the second
+// is the regular expression matcher taking a regular
+// expression and a string and checks whether the
+// string matches the regular expression
+
+//def ders (s: List[Char], r: Rexp) : Rexp = ...
+
+//def matcher(r: Rexp, s: String): Boolean = ...
+
+
+// (5) Complete the size function for regular
+// expressions according to the specification
+// given in the coursework.
+
+//def size(r: Rexp): Int = ...
+
+
+// some testing data
+
+/*
+matcher(("a" ~ "b") ~ "c", "abc") // => true
+matcher(("a" ~ "b") ~ "c", "ab") // => false
+
+// the supposedly 'evil' regular expression (a*)* b
+val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+matcher(EVIL, "a" * 1000 ++ "b") // => true
+matcher(EVIL, "a" * 1000) // => false
+
+// size without simplifications
+size(der('a', der('a', EVIL))) // => 28
+size(der('a', der('a', der('a', EVIL)))) // => 58
+
+// size with simplification
+size(simp(der('a', der('a', EVIL)))) // => 8
+size(simp(der('a', der('a', der('a', EVIL))))) // => 8
+
+// Java needs around 30 seconds for matching 28 a's with EVIL.
+//
+// Lets see how long it really takes to match strings with
+// 0.5 Million a's...it should be in the range of some
+// seconds.
+
+def time_needed[T](i: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (j <- 1 to i) code
+ val end = System.nanoTime()
+ (end - start)/(i * 1.0e9)
+}
+
+for (i <- 0 to 5000000 by 500000) {
+ println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))))
+}
+
+*/
+