Подскажите алгоритм или может у кого-нибудь есть такая задачка(что врятли). Проверка скобок осуществляться должна не через стек,а именно через деревья. Заранее спасибо. [Ответ]

ды искала уже,где только не искала...по существу ничего не нашла.. в основном рассматриваются алогритмы через стек, а то и вобще безо всяких излишеств. [Ответ]

Тенка, Скажи преподу, что гланды через попу тоже говорят, что удаляют. Колько есть более простой способ. [Ответ]

Сообщение от Тенка:
Подскажите алгоритм или может у кого-нибудь есть такая задачка(что врятли). Проверка скобок осуществляться должна не через стек,а именно через деревья. Заранее спасибо.

1 курс ПММ, лекции г-жи Усковой.
Так же была такая синяя книженция с решения всех типовых задач такого рода. [Ответ]

у меня нет знакомых с пмм((( [Ответ]

МММ, а можно такой вопросик: скобки проверяются в тексте или в формуле? [Ответ]

Сообщение от Тенка:
роверка скобок осуществляться должна не через стек,а именно через деревья

а это где такой изврат делать заставляют? [Ответ]

на фкне((((((( [Ответ]

Тенка, Зачем ты себя мучаешь? Может быть тебе лучше в кулинарный техникум пойти? Там не такие сложные задания. Ты сама сможешь с ними справляться. [Ответ]

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

Тенка, алгоритм "на пальцах" МОЕ ИМХО!!!

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

ну можно еще ченить придумать...

PS. Если совсем трудно, могу специально для тебя написать решение... тока скажи на каком языке надо. [Ответ]

Тенка, так всё-таки : проверка в формуле или в тексте??? Если в тексте, то так , как описал MadFish ( приблизительно). И можно вроде даже не загоняться по поводу того, какая скобка какой соответствует. Просто для каждой скобки брать ближайшую после нее закрывающую и ставить ей в соответствие. Если ничего не останется, то всё хорошо (просто проверяем, что нет такого "((...)" или вот такого "() ... )(")
А если должна получиться правильная формула, то тут всё гораздо сложнее: придется строить дерево-формулу.И уже по ней смотреть, что к чему(имхо, в процессе построения скобки и отловятся, но я еще не думала). Жду уточнения условия.))) [Ответ]

ммм...сейчас...проверка осуществляется в формуле...текст типа a или b или c в скобках типа () или {} или []. то естть правильными будут являться конструкции и (а)(b) и {[(a)]}{c} . По сути символы роли не играют.Проблема заключается в проверке расстановок скобок.
MadFish, у меня была такая идея,только раз скобок три типа то сравнивать надо будет элементы одного уровня.Но такой алгоритм не работает для к примеру этого случая {[(a)]}{c} ((((. Я написала программу которая проверяет все через стек...Но не знаю как использовать деревья в данном случае...Ведь через стек все понятно и быстро. ВОт.


Зы: DElphi [Ответ]

Тенка, Ооооо, так скобок у нас 3 вида, это интереснее... Правильно сформулированное условие задачи есть 50% решения.
Понятно, что через стек проще и быстрее, но в задаче есть слово "деревья"
В таком случае Ваш добрый препод прозрачненько так намекает, что неплохо бы построить дерево синтаксического разбора (подробнее Альфред Ахо, Рави Сети, Джеффри Ульман "Компиляторы: Принципы, Технологии, Инструменты" http://masterpc.alfaspace.net/books/..._kompilyators/ )
"на пальцах"
Строим дерево по такому принципу...
Как и раньше работаете со стеком, НО в момент свертки (когда происходит операция POP и из стека извлекается очередной операнд) пришедший и извлеченный из стека операнды становятся "листьями" дерева, а в стёк загоняется фиктивный операнд, обозначающий все выраженье целиком (и этот фиктивный операнд становится "корнем" для полученных "листьев"). В итоге получится дерево из фиктивных операндов на самом нижнем уровне которого будут все ваши скобочки. А проверка в этом случае еще тривиальнее. Если такое дерево построить смогли, значит зер гуд, иначе «отвали моя черешня».
Ну либо (если не делать проверки при создании дерева на правильность вложения) после построения пробежать по последнему уровню дерева и посмотреть чтобы "рядышком" стояли скобочки одинакового типа .

Можно использовать и нисходящий анализ, тогда можно обойтись без стека и строить дерево сразу. Если надо могу описать алгоритм.

PS. Решение нарисуешь сама или мне накорябать? [Ответ]

сама попробую разобраться. спасибо большое за помощь!!!
зы:если не получится,то буду благодарна еще и за кусочек решения [Ответ]