Algorithmic quiz: check a 3-braces expression

[singalen]

Originally published at Fiberglass flowers. You can comment here or there.

I just won a bet for $10 by solving a quiz:

Check the correctness of a braces, brackets and parentheses sequence. The solution should be of linear complexity (to say more, it’s 1-pass).

For instance, these expressions are correct: “()”, “()()[]“, “([][][]{})”, “([])()[]“, and these are not: “][”, “())(”, “(()”.

It’s basically solved in 15 lines, all others being auxiliary. Can you reproduce the algorithm?

The solution follows.

Read the rest of this entry »

Comments

[green-serpent.livejournal.com]

А что сложного?

[singalen]

Ничего, кроме как оценить необходимую структуру данных.

[singalen]

Для алгоритма, конечно. Исходная - это строка :)

[singalen]

А ну ж?

[singalen]

Предложил бы ещё на $10, но не понял, что значит "проще".
Выбросить валидацию данных? Заменить switch на таблицу? Вытянуть короткие функции в одну строку? :)

[singalen]

Попробуй ещё такой: ({[}])

[rioman.livejournal.com]

А рекурсией?
Структура там, конечно, такая же, но неявно.

[singalen]

С рекурсией тоже можно, но немного излишне.

[muwlgr.livejournal.com]

Там есть немножко лишнего. matching(c) вызывается только с предусловием isClosing(c), поэтому case для открывающих скобок там не нужны.
Когда в языке есть синтаксический сахар типа инлайновых конструкторов хэшей, регулярных выражений и пр., всё получается короче (буквальный перевод на Ruby) :

def isCorrect(s)
lastBrace=[]
s.each_char { |c|
if c =~ /^(\{|\[|\()$/ # opening
lastBrace.push c
elsif c =~ /^(\}|\]|\))$/ # closing
return false if lastBrace.size == 0 || { '('=>')', '['=>']', '{'=>'}' }[lastBrace.last] != c # matching
lastBrace.pop
else return false;
end
}
return lastBrace.size == 0
end

# testing :

p [
isCorrect("()") == true,
isCorrect("[]") == true,
isCorrect("{}") == true,
isCorrect("([])") == true,
isCorrect("()()[]") == true,

isCorrect("([][][]{})") == true,
isCorrect("(()[()]())") == true,
isCorrect("([])()[]") == true,

isCorrect("([]") == false,
isCorrect("[]]") == false,

isCorrect("][") == false,
isCorrect("(][)") == false,
isCorrect("(][)") == false,

isCorrect("(][)") == false,
isCorrect("[(){}}") == false,

isCorrect("][") == false,
isCorrect("((") == false,

isCorrect("(()))") == false,

isCorrect("{}{}}{") == false ]

в целом алгоритм со стеком выглядит окончательным и обжалованию не подлежащим :>