Две задачи на использование стека

В недавних публикациях в нашей газете [1–5] были рассмотрены вопросы, связанные с так называемым “стеком” — структурой данных, в которой реализован принцип “последним пришел — первым вышел” (по-английски — “Last In First Out”, или LIFO). Рассмотрим методику решения средствами программирования двух задач, связанных с применением такой структуры данных.

Задача 1. Используя стек, напечатать символы некоторой величины строкового типа в обратном порядке.

С использованием стека задача решается следующим образом. Каждый символ заданной величины, начиная с первого, размещаем в стеке. В результате на вершине стека окажется последний символ, “под” ним — предпоследний и т.д. Извлекая символы из стека, выводим их на экран в порядке, обратном исходному.

В программе на школьном языке программирования (“КуМир”) используем два вспомогательных алгоритма для работы со стеком:

— Поместить — реализует размещение в стеке нового символа;

— Извлечь — осуществляет извлечение элемента из стека (извлекаемое значение является результатом алгоритма-функции символьного типа).

Учтем, что программная реализация этих алгоритмов значительно упрощается, если добавление нового значения в стек и извлечение значения на его вершине проводить в конце заполненной части массива:

алг Поместить(арг сим симв)

нач

· |Увеличиваем значение величины вершина

· вершина := вершина + 1

· |Записываем на вершину стека

· |очередной символ

· стек[вершина] := симв

кон

алг сим Извлечь

нач

· |Значение функции

· знач: = стек[вершина]

· |Уменьшаем значение величины вершина

· вершина := вершина — 1

кон

где:

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

цел nmax; nmax := 100

сим таб стек[1:nmax]

— вершина — индекс элемента массива, являющегося вершиной стека; описание этой величины:

цел вершина; вершина := 0

Создадим также функцию, возвращающую результат логического типа в зависимости от того, пуст стек (истина) или нет (ложь):

алг лог СтекПуст

нач

· знач := вершина = 0

кон

С использованием созданных вспомогательных алгоритмов главная программа принимает вид:

алг Строка в обратном порядке

нач лит строка, цел i

· вывод "Введите строку символов "

· ввод строка

· |Размещаем символы в стеке

· нц для i от 1 до длин(строка)

· · Поместить(строка[i])

· кц

· вывод нс, "Строка в обратном

порядке символов:"

· |Извлекаем символы из стека

· нц пока не СтекПуст

· · вывод Извлечь

· кц

кон

Задача 2. Написать программу, которая определяет, является ли введенная скобочная структура правильной. Примеры правильных скобочных выражений: (), (())(), ()(), ((())), неправильных — )(, ())((), (, )))), ((()).

Можно рассуждать так. Рассматриваем последовательно каждый символ заданной величины слева направо. Если очередной символ — левая скобка, то размещаем ее в стеке, если правая — то извлекаем элемент из стека (это обязательно должна быть левая скобка). После рассмотрения всей строки, если все правильно, стек должен оказаться пустым.

Обсудим особенности вспомогательных алгоритмов.

Так как в стеке размещается только левая скобка, то алгоритм Поместить можно оформить как алгоритм без параметров:

алг Поместить

нач

· вершина := вершина + 1

· стек[вершина] := "("

кон

Поскольку в отличие от первой задачи здесь значение на вершине не используется, то алгоритм Извлечь целесообразно оформить не в виде функции:

алг Извлечь

нач

· |Уменьшаем значение величины вершина

· вершина := вершина — 1

кон

Однако при таком оформлении алгоритма Извлечь главная программа:

цел nmax; nmax := 30

сим таб стек[1:nmax]

цел вершина

вершина := 0

алг Проверка правильности записи скобок

нач лит выражение, цел i

· вывод "Введите скобочное выражение "

· ввод выражение

· нц для i от 1 до длин(выражение)

· · если выражение[i] = "("

· · · то

· · · · Поместить

· · все

· · если выражение[i] = ")"

· · · то

· · · · Извлечь

· · все

· кц

· если СтекПуст

· · то

· · · вывод нс, "Выражение правильное"

· · иначе

· · · вывод нс, "Выражение неправильное"

· все

кон

— будет работать неправильно (убедитесь в этом, проанализировав приведенные далее разъяснения!). Дело в том, что когда в выражении встретится “неправильная” правая скобка, то при ее извлечении из стека значение величины вершина станет отрицательным, и последующее размещение в стеке левой скобки провести не удастся (при выполнении программы появится сообщение об ошибке, связанное с выходом за левую границу массива). Ввести в алгоритм Извлечь вывод на экран сообщения “Стек пуст!”, как это делалось в статье [1], нельзя — при этом ошибка сохранится.

Чтобы зафиксировать факт появления “неправильной” правой скобки, введем в заголовок процедуры Извлечь величину логического типа с именем успешно (имеется в виду, что извлечение элемента на вершине прошло успешно). Пока ошибка не найдена, то успешно = истина (на школьном языке программирования значение истина обозначается как да), если найдена — успешно = ложь (нет).

алг Извлечь(арг рез лог успешно)²

нач

· если вершина > 0

· · то

· · · |"Извлекаем"

· · · вершина := вершина — 1

· · · |Извлечение прошло успешно

· · · успешно := да

· иначе

· · |Извлечь нельзя

· · успешно := нет

· все

кон

C учетом этого в главной программе следует использовать оператор цикла с предусловием:

алг Проверка правильности записи скобок

нач лит выражение, цел i, лог успешно

· вывод "Введите скобочное выражение "

· ввод выражение

· успешно := да |Условно

· i := 1

· нц пока i <= длин(выражение) и успешно

· · если выражение[i] = "("

· · · то

· · · · Поместить

· · все

· · если выражение[i] = ")"

· · · то

· · · · Извлечь(успешно)

· · все

· · i := i + 1

· кц

· если СтекПуст

· · то

· · · вывод нс, "Выражение правильное"

· · иначе

· · · вывод нс, "Выражение неправильное"

· все

кон

Внимание! Приведенная программа также будет работать неправильно, но уже по другой причине. Если даже скобочное выражение будет неправильным, то после “правильной” работы алгоритма Извлечь значение величины вершина останется равным 0, из-за чего функция СтекПуст будет истинной, и на экран выведется сообщение “Выражение правильное”. Ясно, что критерием правильности заданного выражения является тот факт, что стек пуст, и при этом все операции по извлечению скобок прошли успешно. Это означает, что при выводе результата проверки следует использовать сложное условие:

· …

· если СтекПуст и успешно

· |Если все извлечения

· |прошли успешно

· · то

· · · вывод нс, "Выражение правильное"

· · иначе

· |Была ошибка

· · · вывод нс, "Выражение неправильное"

· все

кон

Примечание. Аналогично можно решить задачу: “Дана линейная запись арифметического выражения, в котором использованы только круглые скобки. Проверить правильность расстановки скобок в выражении”. Такую задачу решает транслятор, анализируя программу на языке программирования высокого уровня.

Задания для самостоятельной работы

1. Дана величина a строкового типа из четного количества символов. Получить и напечатать величину b, состоящую из символов первой половины величины a, записанных в обратном порядке, после которых идут символы второй половины величины a, также записанные в обратном порядке. Например, при а = “привет” b должно быть равно “ипртев”.

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

3. Проверить правильность расстановок скобок в выражении, использующем скобки вида: “(”, “)”, “{”, “}”, “[”, “]”. Требование вложенности скобок разного вида не учитывать, т.е., например, последовательности скобок “({})[]” и “([{()}]}” — правильные.

4. В статье [6] отмечалось, что при нахождении делителей натурального числа количество проверок возможных делителей можно существенно сократить, если учесть, что у каждого делителя d числа n, не превышающего , есть “симметричный” ему делитель, получающийcя в результате деления n на d. Например, если n = 30, достаточно найти делители 1, 2, 3, 5 (целая часть квадратного корня из 30 равна 5), а все прочие делители получаем следующим образом:

30 div 1 = 30;

30 div 2 = 15;

30 div 3 = 10;

30 div 5 = 6.

Правда, если выводить на экран найденные делители и “симметричные” им, то, например, при n = 30 на экран будет выведено:

1 30 2 15 3 10 5 6

Составить программу, в которой все делители заданного числа n будут выводиться в порядке возрастания (при проверке возможных делителей, не превышающих

).

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

Литература

1. Насыров Н.А. Стек — первое знакомство. / “В мир информатики” № 129 (“Информатика” № 17/2009).

2. Насыров Н.А. Учим стек вычислять. / “В мир информатики” № 130 (“Информатика” № 18/2009).

3. Насыров Н.А. Cтек и компьютер. / “В мир информатики” № 132 (“Информатика” № 20/2009).

4. Формирование постфиксного выражения. / “В мир информатики” № 132 (“Информатика” № 20/2009).

5. Насыров Н.А. Вычисление постфиксного выражения. / “В мир информатики” № 133 (“Информатика” № 21/2009).

6. О расчете количества делителей. / “В мир информатики” № 131 (“Информатика” № 19/2009).

---

² В языке программирования Паскаль соответствующая процедура при аналогичном оформлении заголовка называется “процедура с параметром-переменной успешно” (естественно, имя парамет­ра должно быть другим)