А можно для тупых, поподробнее? Звёздочка обозначает помещение в стек — чего? Предшествующей буквы? А извлечение из стека?

Он сам откуда знает? Человеку нужно решение задачи, которую ему задали в его учебном заведении. Еще и код хочет готовый.

Э… август на дворе, какое учебное заведение?

Вот именно!

Вообще-то я занимаюсь самообразованием, дорогие мои!

Да. Извлечение - буква без последующей звездочки.

Задача из Седжвика, помечена как «высокого уровня сложности».

Какойто непонятный задача. Что такое последовательность стековых операций? A так понял, что есть последовательности {a} и {b} и некий возможный набор операций над ними. Надо определить можно ли при помощи произвольного количества этих операций получить из {a} {b}. Вот в операциях и суть неопределенность. Что можно, а что нельзя?

«peal» и «leap» нам просто достаточно поменять местами вершину и дно стека

Как по мне так тут стек - лишнее. Комбинаторика. {peal} это вариант перестановки {leap}. Если поменять местами дно и вершину стека это стековая операция - озвучь все.

то?

есть входная последовательность букв

и две операции и команда(по терминатору строки)

* - помещение очередной буквы из инпута в стек.

= - перенос очередной буквы из инпута в аутпут.

. - перенос из стека в аутпут содержимого стека поэлементо пока есть чё popить(эта операция есть всегда последняя операция в управляющей строке)

Вопрос дана входная последовательность и выходная последовательность , ваша программа должна сгенирировать «управляющую строку » переводящую входную в выходную или показать по какой причине такая строка не существует.

По книге у нас есть две стековые операции: push и pop, также мы можем перемещать указатель стека на произвольное число элементов из которых он состоит. Вроде все.

То, что этот алгоритм с комбинаторным уклоном я и сам догадываюсь, но математически выразить не могу :)

Где-то туда :) Спасибо, за участие. Мне всегда приятно видеть умных людей.

Толсто же!

дык это задача на сортировку вагонов когда есть только 1 тупик и 1 прямой путь

т.е картинка

путь идущий прямо и у него есть поворот в середине в тупик и выезд из тупика.

по условию выезжать(из тупика) может только 1 состав ибо толкач в самом начале в тупике и выталкивает только 1 раз для приехавшего поезда.

решение очевидно

мы можем перемещать указатель стека на произвольное число элементов из которых он состоит

Прости, если я кажусь тупым, но такая операция + pop позволяет получить произвольный элемент «стека». Т.е. узнать есть ли решение для двух данных последовательностей можно просто отсортировав их и сравнив?

например - «peal» и «leap» нам просто достаточно поменять местами вершину и дно стека

Это ж как так поменять? И какой стек: нормальный LIFO?

1. делаем последовательно push:

char *str = "peal";
while(*str) push(*str++);
// все, в стеке p,e,a,l

2. Чтобы делать произвольные махинации со стеком, нам придется добавить операции "пропуска" элементов стека (либо завести дополнительный стек), а также для простоты сделать стек двунаправленной очередью:

char newstr[5] = {0}; 
newstr[0] = pop(); // в стеке p,e,a
char tmp = pop();  // tmp = a, в стеке p,e
newstr[1] = pop(); // в стеке p, newstr = "le"
newstr[2] = tmp;   // newstr = "lea"
newstr[3] = pop(); // стек пустой, newstr = "leap"

Честно, вот тут я сам немного не понял автора.

Судя по всему у него там не стек, а массив, которому можно оторвать конец. Но тогда задача получается слишком простой.

Эдуард, возможно я покажусь Вам наркоманом, но вчера действительно я сделал это предположение так, будто мы можем вытолкнуть из стопки произвольный элемент. А не только тот, который на верхушке «стопки».

Каюсь. Да.

Но нельзя решить задачу не поняв условия. У тебя по описанию выходит массив. Решение это просто индекс элемента из {b} в {a}?

Нет, таки стек. Это мой пытливый ум исказил постановку автора.

А какой смысл иметь '*' и '=', когда есть '.'? Чтобы иметь возможность копировать стек поэлементно? Но последовательность же не изменится. Нужны «регистры» в которых можно переставлять символы, и вопрос только в том, сколько регистров.

Тогда [выше написал] как можно менять порядок символов?

Ну потому и указано, что задача последнего уровня сложности, гы!

последнего уровня сложности

Принеси мне то, не знаю что? А ты точно всю задачу переписал, и что всетаки значит «стековая операция»? Просто пушем и попом можно скопировать часть стека, или весь стек в другой стек. Последовательность символов ты никак не поменяешь. Может они имеют ввиду что {b} это подпоследовательность {a}?

Я же не маленький. Конечно точно.

В общем, примерно это уже описано здесь: http://informatics.mccme.ru/mod/statements/view3.php?id=1278&chapterid=855

В общем, примерно это уже описано здесь

Так там тупик дает возможность доступа к произвольному элементу. Чтобы получить n-й элемент на вершине, нужно сложить n-1 в тупик. Единственно может можно это дело как-то оптимизировать. И есть ограничение:

так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2

А у тебя такого ограничения нет.

* это push

. это popall

А как менять элементы местами? В задачке про поезд есть тупик. А тут как?

Прочитал тред, не понял qulinxao правильно изложил твою задачу или нет?

добавить звездочку

Одну?

не понял qulinxao правильно изложил твою задачу или нет?

peal -> leap - не получится.

Поскольку формулировка туманная, будем считать, что правильно.

Вот интересный документ на эту тему: http://goo.gl/ksBml2

Это уже не стек, а связный список!

Да. Он самый.

Не до конца понял условие но

1. Прямой перебор
2. Метод ёжиков.

2. Метод ёжиков

А вот с этого места поподробней.

Тогда не дезинформируй людей и не пиши "стек".

А с двунаправленным списком любые манипуляции можно влегкую делать.

По сути оптимизация перебора.

Если я правильно понял то есть 2 операции (a и b), каждая из них рождает перестановку строки. Требуется найти цепочку перестановок S0 в Sn.

1. Создаём множество перестановок {S0} (пока там только одна перестановка S0) и пустое пока множество {U}
2. Применяем ко всем элементам множества {S0} операции a и b, результатом становится множество {S1}
3. Если среди элементов {S1} есть Sn значит цепочка операций найдена (порядок операций естественно нужно хранить). Всё.
4. Считаем число элементов {U}
5. Добавляем {S1} в {U}
6. Считаем число элементов {U}, если оно не изменилось - задача не имеет решения. Всё
7. Повторяем начиная с п2 для {S1}

Лень вникать в условия задачи, это первый способ который пришёл в голову.

Хм, я же выше написал, что это было мое своеволие. А в оригинале у автора стек. В этом и сложность. Вот.

В стеке нет операции доступа к произвольному элементу! Только push и pop!

Спасибо!

Ну дык вроде с сортировкой вагонов тоже нет произвольного доступа к ним, так?

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

Там используется несколько стеков!

Скажем, в задаче ханойской башни стека три. И задача полностью решается (но за очень большое время). Чем больше промежуточных стеков, тем шустрей можно выполнить произвольную перестановку элементов.

Да, так точно.

Понял. Спасибо.

Правильно. Ведь ограничения на количество стеков в задаче нет.

Все сходится :)

Предлагаю такой алгоритм (undestructive_pop — прочитать вершину стека, не опустошая):

1. на вход задаем исходное слово и нужное.

2. побуквенно просматриваем исходное слово:

2а. если буква исходного совпадает с первой незаполненной нужного, заполняем, переходим дальше; 2б. если стек пуст, делаем push текущей буквы, переходим дальше; 2в. если undestructive_pop не совпадает с нужной, делаем push; 2г. иначе делаем pop;

3. проверяем, заполнили ли мы полностью требуемое слово. Если заполнили — возвращаем TRUE, иначе — FALSE.

Добро. Обмозгую на досуге.

Это для одного стека. Могу сейчас попробовать код набросать.

Для нескольких стеков уже задача посложней — бери алгоритм ханойской башни.

ОК!

Тут вроде тоже неплохо описано, не?

Задачка достаточно сложная :) (комментарий)