Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Обобщение правильных скобочных последовательностей / 7 сообщений из 7, страница 1 из 1
02.10.2009, 13:38:34
    #36229544
Naf
Naf
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обобщение правильных скобочных последовательностей
Для символов L[1],L[2],...,L[K],R[1],R[2],...,R[K] строка считается правильной, если:
1. она пустая
2. может быть построена по правилам:
2.1. если S - правильная строка, то L[i]+S+R[i] - правильная
2.1. если S1, S2 - правильные строки, то S1+S2 - правильная

Требуется:
1. Для произвольной строки определить, что она правильная
2. Для числа N определить число правильных строк длины 2*N

С уважением, Naf
...
Рейтинг: 0 / 0
02.10.2009, 16:02:20
    #36229931
Naf
Naf
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обобщение правильных скобочных последовательностей
ну все, первая решена через стек, вторая найдена в википедии
С уважением, Naf
...
Рейтинг: 0 / 0
02.10.2009, 19:54:48
    #36230372
Roman S. Golubin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обобщение правильных скобочных последовательностей
Nafну все, первая решена через стек, вторая найдена в википедии
С уважением, Naf

spoj насилуете?
...
Рейтинг: 0 / 0
02.10.2009, 21:46:04
    #36230461
RAndrew
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обобщение правильных скобочных последовательностей
1:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
import Text.ParserCombinators.Parsec
import Control.Monad
import Data.List

left = "([{"   -- |список левых скобок
right = ")]}"  -- |список правых скобок

check = (do
    l <- oneOf left
    check
    r <- oneOf right
    when (elemIndex l left /= elemIndex r right) $ fail ""
    check)
  <|> return ()

isRightString s =
    case parse (check>>(char '\n')) "" (s ++ "\n") of
        Left _ -> False
        Right _ -> True

2: не понял, N -- это число скобок?
...
Рейтинг: 0 / 0
03.10.2009, 02:58:23
    #36230589
Roman S. Golubin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обобщение правильных скобочных последовательностей
Эта. К чему я про spoj завел разговор: http://www.spoj.pl/problems/FOOL/
...
Рейтинг: 0 / 0
03.10.2009, 13:24:04
    #36230715
belugin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обобщение правильных скобочных последовательностей
RAndrew1:
Код: plaintext
1.
import Text.ParserCombinators.Parsec


Сильно! Вот как надо работать со строками, без монады не разберешься!

а нельзя как-нибудь типа:

Код: plaintext
1.
2.
isGood "" = true
isGood x:xs = ((elemIndex x left) ==  (elemIndex (lastChar xs) right)) and (isGood (middlePartOf xs))
...
Рейтинг: 0 / 0
03.10.2009, 15:04:16
    #36230787
RAndrew
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обобщение правильных скобочных последовательностей
belugin
Код: plaintext
1.
2.
isGood "" = true
isGood x:xs = ((elemIndex x left) ==  (elemIndex (lastChar xs) right)) and (isGood (middlePartOf xs))

Вряд ли. Кроме того, что lastChar тяжелая функция, которую ленивость не спасет, так еще
Код: plaintext
isGood "{[]}()" = False
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Обобщение правильных скобочных последовательностей / 7 сообщений из 7, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]