ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Valentin Kononov                     2:5035/38.9    30 Jan 2002  00:07:05
 To : Stanislav Aranovsky
 Subject : re: Посоветyйте алгоpитм, очень надо!!!
 -------------------------------------------------------------------------------- 
 

 Вcк Янв 27 2002 01:39, you wrote to Aleksey Nilov:
 
  AN>> Имеется задача:
  AN>> Дана стpока, состоящая из скобок 4-х видов (,),[,]
  AN>> Опpеделить минимальное число скобок, котоpые надо подставить в стpокy,
  AN>> чтобы она стала "пpавильной"...
  AN>> Hапpимеp:
  AN>> "[ ( ] )" - "непpавильная стpока"
  AN>> "[ ] ( [ ] )" - "пpавильная", полyченная пyтем подстановки в
  AN>> "непpав-ю" 2-х скобок! Интеpесyет алгоpитм... yсловие - сложность <=
  AN>> O(N*N), а желательно O(N*log N)
  SA>
  SA> В пpинципе, я тyт так подyмал, задача pешается за O(n) pекypсивным
  SA> методом.
 
   Во-первых, условие неоднозначно. Приведенную строчку можно исправить и
 так: "[ ( ) ] ( )" или так "[ ( [ ] ) ]". Так что стоит доопределить - есть
 ли иерархия у скобок, например. Hо O(N) хватит, ИМХО, в любом случае.
 1) Проще всего действовать тривиально:
 нашел скобку, подставь рядом (либо слева, либо справа) парную :))
 2) А реально примерно так. Держим стек, в который записываем все открывающиеся
 скобки. Если же находим закрывающуюся, смотрим верх стека. Если там скобка того 
 же типа, выкидываем ее, если другого или стек пуст, то ставим перед этой парную 
 открывающуюся. Когда строка кончится, вываливаем из стека все, что накопилось
 (разумеется, при записи или чтении каждую скобку надо перевернуть или просто
 писать туда 0-1) и идем за пивом.
 3) Если же задана иерархия, например, квадратные скобки не содержат круглых
 (как в авторском примере), то все еще проще: держим 2 счетчика открытых скобок, 
 если счетчик квадратных не пуст, то новых круглых открывать нельзя, а след-но,
 перед их открытием надо закрыть все квадратные.
 ЗЫ: В первом и третьем вариантах строка получится длиннее - в первом примерно в 
 1.5 раза, в 3-ем - в 1.25 (на глазок). А во втором - минимально необходимая
 длина (тоже раза в полтора больше исходной, неправильной строки).
 
  С уважением, Valentin
 
 --- * ---
  * Origin:  Пейте соки и нектары GSM  (Kursk 2:5035/38.9)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Посоветуйте алгоритм, очень надо!!!   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