Интересная задача

[SadBrick]

Задачи с применением стека

Проверка расстановки скобок
a) Дана последовательность круглых, фигурных и квадратных скобок.
Необходимо проверить правильность данной последовательности.
Например, {}[(){}] - правильная последовательность, {[}] - неправильная.

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

АТД - Стек Представление - Массив

[ViktorR]

Тема тут уже обсуждалась. Надо поискать.
Но если лень искать тут, то могу порекомендовать найти книгу:
А.Шень, Программирование, Теоремы и задачи, Москва, МЦНМО, 2004 - эта версия у меня.
Там на стр.97 изложен алгоритм решения.
Идея:
1. Закодировать скобки по следующему правилу:

(   1
[   2
{   3
)  -1
]  -2
}  -3

2. В процессе анализа строки укладываем открывающиеся скобки (их код) в стек.
3. При обнаружении закрывающейся скобки лезем в стек. Если стек пуст - ошибка.
4. Считанный из стека код сравниваем с кодом закрывающейся скобки. Если неравно - ошибка.
Сравнение - через сложение или типа:

 Err := (t <> -a[i]);

5. Ели достигнут конец строки и стек пуст - Ок, иначе - ошибка.


Как-то так, ...

[Poma][a]

Ну
1) нисходящий рекурсивный анализ
2) как уже сказали, динамика со стеком..

[Serge_Bliznykov]

а что интересного в этой задаче?
заводим стек. перебираем по одному символы в строке, если встретили скобочку - если она открывающая - поместили её в стек, если она закрывающая, вытащили элемент с верхушки стека и проверили, что вытащилась скобка того же типа, что и открывающаяся (круглая, квадратная, фигурная), только ОТКРЫВАЮЩАЯ.
Если тип скобок не совпал - выдаём ОШИБКУ (последовательность неправильная) и прекращаем цикл.
Если успешно дошли до конца набора символов (строки), проверяем, пустой ли стек.
Если пустой - БИНГО! Последовательность правильная, если стек после строки не пустой - ошибка (последовательность неправильная).
Всё.

ups!//
я опоздал со своим ответом. Уже верные ответы даны!

[SadBrick]

Книгу нашёл спасибо) постараюсь разобраться

ну все равно спасибо за ответ, мб и твои вклады пригодяться)

_________
Не надо плодить подряд несколько коротких сообщений!
Это нарушение правил...
для того, чтобы через минуту/другую дописать сообщение,
не надо создавать ещё один новый пост.
нажимайте на предыдущем кнопку "Редактировать" ("Правка")
и дописывайте в своё сообщение, что Вы хотели добавить!

Модератор