typo

Spacinator.scala

import scala.collection.mutable.Map

object Worder {
  val Dict = List("a", "pot", "toe", "potatoe", "to")
  
  // used for memoization in isParsable()
  val memo = Map.empty[String, Boolean]

  def main(args: Array[String]) {
    printParseTree(new ParseTreeNode("", parse("apotatoe")))
  }
  
  class ParseTreeNode(val word: String, val offspring: List[ParseTreeNode])

  // true if the given string is fully parsable into a pseudo-sentence
  def isParsable(str: String): Boolean = {
    return isParsable(str, 1)
  }
  
  def isParsable(str: String, w: Int): Boolean = {
    if (memo.contains(str))
      return memo(str)

    if (w < 1) {
      memo(str) = false
      return false
    } else if (isWord(str)) {
      memo(str) = true
      return true
    } else {
      if (w > str.length())
        return false

      val head = str.substring(0, w)
      val tail = str.substring(w)

      if (head.length() == 0 || tail.length() == 0)
        return false

      return isParsable(head, w) && isParsable(tail, w) ||
        isParsable(head, w - 1) && isParsable(tail, w - 1) ||
        isParsable(str, w + 1)
    }
  }

  // parses the given string into a List of ParseTreeNodes, representing all of the possible parsings
  def parse(str: String): List[ParseTreeNode] = {
    val windows = 1 to str.length()
    val permutations = (str, "") :: windows.map((w) => (str.substring(0, w), str.substring(w))).to[List]
    return permutations.flatMap(parsePermutation)
  }

  // FIXME: this should probably be an anonymous function in parse(), but wasn't sure how to use that with flatMap() properly
  def parsePermutation(tuple: (String, String)): Option[ParseTreeNode] = {
    val head = tuple._1
    val tail = tuple._2

    if (isWord(head) && isParsable(tail)) {
      val r = parse(tail)
      if (isWord(tail)) {
        Some(new ParseTreeNode(head, parse(tail) :+ new ParseTreeNode(tail, List())))
      } else {
        return Some(new ParseTreeNode(head, parse(tail)))
      }
    } else {
      return None
    }
  }
  
  // print the given parse tree, starting at the given ParseTreeNode
  def printParseTree(root: ParseTreeNode) {
    printParseTree(root, "")
  }

  def printParseTree(root: ParseTreeNode, sentence: String) {
    val acc = sentence + root.word + " "
    if (root.offspring.length == 0) {
      println(acc)
    } else {
      root.offspring.foreach((n) => {
        printParseTree(n, acc)
      })
    }
  }
  
  // true if the given string is a complete word
  def isWord(str: String): Boolean =
    Dict.contains(str)
}