# HG changeset patch # User Christian Urban # Date 1543425220 0 # Node ID 44161f2c322627e4949c49d1703fbfcb3d3ceda3 # Parent 22705d22c1057893dd3f3c5ea6ab1df02f8d3a40 updated diff -r 22705d22c105 -r 44161f2c3226 templates4/postfix.scala --- /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 + + + + diff -r 22705d22c105 -r 44161f2c3226 templates4/postfix2.scala --- /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 diff -r 22705d22c105 -r 44161f2c3226 templates4/re.scala --- /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)))) +} + +*/ +