|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilya Potrepalov 2:5020/400 31 Jan 2002 13:11:33
To : Ilya Potrepalov
Subject : Re: Посоветуйте алгоритм, очень надо!!!
--------------------------------------------------------------------------------
Ilya Potrepalov сообщил в новостях следующее:
> Можно и так. Hо тут можно и по-другому попробовать. Сам я далек от этого, но
> кое-какие мысли у меня появились.
>
> Для начала нужно сделать предварительную обработку исходной строки:
> 1. Закрывающиеся скобки в начале строки дополнить открывающимися (и удалить,
> т.е. дальше их учитывать не нужно).
> 2. Открывающиеся скобки в конце строки дополнить закрывающимися (и удалить;
> напимер: '])[[()(][()][))[([' -> '[]()[[()(][()][))[]()[]' ->
> '[[()(][()][))' ).
> 3. Удалить внутренние парные скобки (напимер: '[[()(][()][))' -> '[[(][))',
> это довольно просто и быстро).
>
> А далее... Тут можно проанализировать, как человек решает такую задачу.
Здесь еще можно шаг добавть. Если ближайшая к началу закрывающаяся (к
окончанию - открывающаяся) скобка не имеет соответствующей 'парной' скобки, то
ее тоже легко можно дополнить и удалить. Hапример: '((]([(]]' ->
'()()[]()[()]]' -> ']' -> '[]' (круглые скобки не имеют соответствующих
закрывающихся скобок, поэтому они сразу дополняются; а вот из квадратных -
только одна не имела соответствующей открывающейся скобки).
> Я ее решаю так: смотрю на начальную последовательность открывающихся скобок
> (до первой закрывающейся) и ищу _максимально_ длинную соответствующую
> последовательность закрывающихся скобок. И тоже их 'сокращаю'. Hапример:
Опс. А вот здесь не так. Сначала нужно искать максимально длинную
последовательность скобок одного направления (открывающихся или
закрывающихся). А потом уже искать ближайшую максимально длинную
последовательность соответствующих скобок. Пример:
([(](((]))))) -> ([( ] ((( ] ))))) ->
-> ([(] ((( ] ))) )) -> ([(] )) -> ([ ( ]) )
> ([)])[(])] -> ([ ) ]) [(])] (пробелы для наглядности)
> ([(([)]])]) -> ([( ([)]] )])
> [[(][)) -> [ [ ( ] [)) или [[ ( ][ ) ) - оба разбиения дают
> одинаковый результат
С учетом дополнения, строки '[[(][))' на этом этапе быть не должно. Она
должна на предыдущем этапе сократиться до '[[(]))'.
> ([(([)]]))][) -> ( [(([ )] ]))] [)
И здесь:
([(([)]]))][) -> ([(([)]]))][]) -> ([(([ )] ]))])
Так что основная сложность - правильно разбить исходную строку на отдельные
фрагменты.
Илья
--- ifmail v.2.15dev5
* Origin: In God we trust. Others must pay. (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Посоветуйте алгоритм, очень надо!!! |
Aleksey Nilov |
24 Jan 2002 20:46:28 |
 Re: Посоветуйте алгоритм, очень надо!!! |
Grandalf Gray |
25 Jan 2002 19:44:12 |
  Re: Посоветуйте алгоритм, очень надо!!! |
Grandalf Gray |
25 Jan 2002 20:52:01 |
 Re: Посоветуйте алгоритм, очень надо!!! |
Aleksey Nilov |
26 Jan 2002 03:00:47 |
|
Re^2: Посоветуйте алгоритм, очень надо!!! |
Sergey Politov |
26 Jan 2002 06:50:50 |
|
Посоветуйте алгоритм, очень надо!!! |
Max Alekseyev |
25 Jan 2002 23:15:54 |
|
Посоветуйте алгоритм, очень надо!!! |
Max Alekseyev |
26 Jan 2002 03:40:34 |
|
Посоветуйте алгоритм, очень надо!!! |
Max Alekseyev |
25 Jan 2002 22:08:58 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Grandalf Gray |
26 Jan 2002 12:46:42 |
|
Посоветуйте алгоритм, очень надо!!! |
Max Alekseyev |
26 Jan 2002 02:30:30 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Grandalf Gray |
26 Jan 2002 12:46:43 |
|
Посоветуйте алгоритм, очень надо!!! |
Max Alekseyev |
25 Jan 2002 22:04:28 |
|
Посоветуйте алгоритм, очень надо!!! |
Aleksey Nilov |
29 Jan 2002 01:53:54 |
 Посоветуйте алгоритм, очень надо!!! |
Max Alekseyev |
28 Jan 2002 16:49:14 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Sergey Politov |
29 Jan 2002 06:34:29 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Aleksey Nilov |
31 Jan 2002 02:43:30 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Ilya Potrepalov |
31 Jan 2002 09:41:58 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Ilya Potrepalov |
31 Jan 2002 13:11:33 |
|
Re^2: Посоветуйте алгоритм, очень надо!!! |
Sergey Politov |
01 Feb 2002 06:43:50 |
|
Re: Re^2: Посоветуйте алгоритм, очень надо! !! |
Ilya Potrepalov |
01 Feb 2002 15:46:36 |
|
Посоветуйте алгоритм, очень надо!!! |
Sergey Ezhov |
26 Jan 2002 14:03:07 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
27 Jan 2002 02:28:38 |
|
Посоветyйте алгоpитм, очень надо!!! |
Sergey Ezhov |
27 Jan 2002 22:36:11 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
28 Jan 2002 14:08:18 |
|
Re: Посоветyйте алгоpитм, очень надо!!! |
Sergey Politov |
30 Jan 2002 07:23:33 |
|
Посоветyйте алгоpитм, очень надо!!! |
Sergey Ezhov |
30 Jan 2002 22:54:47 |
|
Посоветуйте алгоритм, очень надо!!! |
Nickita A Startcev |
30 Jan 2002 02:18:38 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
27 Jan 2002 02:39:02 |
|
Re: Посоветyйте алгоpитм, очень надо!!! |
Sergey Politov |
27 Jan 2002 06:23:28 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
28 Jan 2002 03:18:38 |
|
Re: Посоветyйте алгоpитм, очень надо!!! |
Sergey Politov |
28 Jan 2002 06:46:54 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
29 Jan 2002 15:25:24 |
|
Посоветyйте алгоpитм, очень надо!!! |
Oleg Yanchenkov |
30 Jan 2002 22:03:08 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
01 Feb 2002 02:45:34 |
|
re: Посоветyйте алгоpитм, очень надо!!! |
Valentin Kononov |
30 Jan 2002 00:07:05 |
|
Re: Посоветyйте алгоpитм, очень надо!!! |
Andrew Ezhguroff |
31 Jan 2002 01:40:00 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
31 Jan 2002 02:19:28 |
|
Re^2: Посоветyйте алгоpитм, очень надо!!! |
Sergey Politov |
31 Jan 2002 05:25:21 |
|
re: Посоветyйте алгоpитм, очень надо!!! |
Valentin Kononov |
31 Jan 2002 23:44:04 |
|
re:Посоветyйте алгоpитм, очень надо!!! |
Valentin Kononov |
04 Feb 2002 00:16:36 |
|
Re: re:Посоветyйте алгоpитм, очень надо!!! |
Ilya Potrepalov |
05 Feb 2002 07:58:56 |
|
Посоветyйте алгоpитм, очень надо!!! |
Oleg Yanchenkov |
28 Jan 2002 08:30:07 |
|
Re: Посоветyйте алгоpитм, очень надо!!! |
Sergey Politov |
29 Jan 2002 06:08:00 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
29 Jan 2002 15:27:40 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Michael Leontyev |
29 Jan 2002 14:46:19 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
30 Jan 2002 04:25:30 |
|
Re: Посоветyйте алгоpитм, очень надо!!! |
Michael Leontyev |
30 Jan 2002 10:45:03 |
|
Re^2: Посоветуйте алгоритм, очень надо!!! |
Sergey Politov |
30 Jan 2002 07:55:24 |
|
Посоветyйте алгоpитм, очень надо!!! |
Oleg Yanchenkov |
01 Feb 2002 00:31:21 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Zapadinsky Anatoly \\(ZAB\\) |
30 Jan 2002 18:06:09 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Michael Leontyev |
30 Jan 2002 18:59:35 |
|
|
