english | блог | контакт
Thu, 22 Nov 2012 @ 08:42

Проверка корректности расстановки скобок/кавычек в строке

scala алгоритмы

Вообще-то надо было на python-е и не мне. Но, "само написалось":

val brackets = List(("(", ")"), ("[", "]"), ("{", "}"),
                    ("\"", "\""), ("'", "'"), ("`", "`"));

def checkBrackets(s:String) = {
  def check(s:String, stack:List[String]):Boolean = {
    if (s.length == 0) {
      stack.size == 0
    } else {
      val first = s.substring(0,1)
      if (stack.size > 0 && stack.first == first) {
        check(s.substring(1), stack.tail)
      } else if (brackets.exists(_._1 == first)) {
        check(s.substring(1), brackets.filter(_._1 == first)(0)._2 +: stack)
      } else if (brackets.exists(_._2 == first)) {
        false
      } else {
        check(s.substring(1), stack)
      }
    }
  }
  check(s, List[String]())
}

checkBrackets(" {({({({()})})})}")
true
checkBrackets("{(})")
false

Sat, 09 Jul 2011 @ 07:08

Хвостовая рекурсия в Scala

scala

Жизнь радует необходимостью и возможностью изучать новое и интересное. Например, scala. Знакомство, как это часто бывает, начинается со всяких вычислительных задачек, построения последовательностей, бессмысленной обработки списков, вычисления факториалов, рекурсивных и не очень алгоритмов.
Ага, рекурсия, хвостовая. И она там действительно есть :)

Нашёл "в интернетах", что в scala реализация сей фичи неспешна, проверил. За два года ситуация явно улучшилась.
читать дальше