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

Fri, 12 Feb 2010 @ 12:03

Преобразования ip и netmask

java алгоритмы велосипеды

Чисто из любопытства получился очередной велосипед, умеющий преобразовывать адрес ip в int и обратно в строку + калькулятор маски сети для двух крайних адресов.
читать дальше

Fri, 05 Feb 2010 @ 11:37

Сумма прописью

java алгоритмы

Возникла задачка: преобразовать число (сумму в рублях/долларах/евро) в его словесную форму. И сделать это для русского и английского языка.

Быстрое гугление принесло пачку результатов, из которых хотелось бы выделить эти два:

http://www.freesource.info/wiki/TZ/SummaPropis%27ju& - подборка реализаций на perl/php/python/java/delphi.

http://runcore.habrahabr.ru/blog/76171/ - красивая реализация на java.

Скорее всего я плохо искал, но "универсальной реализации для разных языков" я не нашёл. Поэтому, после некоторого числа мозговых операций, было решено взять за основу имеющееся (вариант от runcore) и преобразовать его для своих нужд.
читать дальше

Tue, 02 Feb 2010 @ 16:56

Построение списка с учётом весов

алгоритмы

Всплыла задачка:
Есть набор некоторых объектов с весами (приоритетом). Требуется сгенерировать последовательность, в которой частота встречи каждого объекта пропорциональна его весу.

Мысль о изобретении велосипеда пришла в голову слишком поздно, потому получились два варианта.
читать дальше

Tue, 28 Jul 2009 @ 16:25

Сортировка больших объёмов данных, FileSort

алгоритмы сортировка

Недавно на Хабре была статья Сортировка миллиона 32-битных int'ов в 2 мегабайтах памяти на Питоне. Заинтересовался, попробовал реализовать на Java.
читать дальше

Sun, 26 Jul 2009 @ 22:15

Облака тегов

алгоритмы блог

Сегодня задумался о необходимости реализации облака тегов. С одной стороны это полезный блок, а с другой - алгоритмически интересная задача.
читать дальше

Tue, 21 Jul 2009 @ 14:20

Подсветка синтаксиса - 2

java regex алгоритмы блог

Как оказалось, простая реализация - не самая корректная. Нашлись некоторые ситуации, которые вызывали забавные сбои, о чём ниже.
читать дальше