В качестве примера рассмотрим следующую задачу. Во всех компиляторах с языков программирования требуется узнавать, является ли произвольное выражение правильно построенным. в частности, нужно определять, правильно ли расставлены в выражении скобки. Например, последовательность ( ) (( ) ( )) представляет правильную последовательность скобок, а ( ) ((( ) ( )) неправильную (есть лишние левые скобки). В более широком математическом контексте в арифметическом выражении обычно встречаются также квадратные скобки [ ] и фигурные скобки { }.
Предположим, что вас попросили разработать алгоритм определения того, что произвольная последовательность круглых, квадратных и фигурных скобок является правильно построенной. Что мы понимаем под правильно построенной последовательностью? Обычное определение состоит в следующем:
1. Последовательности ( ), [ ] и { } являются правильно построенными.
2. Если последовательность х правильно построенная, то правильно построены и последовательности (х), [x] и {x}.
3. Если последовательности xиyправильно построенные, то такова же и последовательность xy.
4. Правильно построенными являются лишь те последовательности, правильность которых следует из конечной последовательности применений правил 1,2 и ,3.
Это определение определяет правильно построенные последовательности конструктивно. Например, следующие последовательности являются правильно построенными:
Обычно, чтобы установить, являются ли выражения такого типа правильно построенными, используют стековую память (или просто стек), которая представляет собой бесконечную в одну сторону последовательность слов памяти, как изображено на рис. 8.
Для запоминания элементов данных в стеке элемент заносят в верхнее слово ТОР (ВЕРШИНА),
сдвигая тем самым вниз (по одному слову) все другие слова, хранящиеся в стеке
(совершенно аналогично тому, как в столовой складывают подносы в стопку). Выбор
элементов данных из стека возможен лишь считыванием по о
дному за раз из слова ТОР, причем все остальные
элементы данных сдвигаются вверх.
Мы не имеем права выбирать элементы данных внутри стека. (В столовой мы обычно не выбираем двадцатый поднос из стопки подносов.) Иногда термин «стек» обозначает стековую память, когда нам разрешено считывать элементы, находящиеся ниже слова ТОР, но не разрешается изменять их значения или добавлять новые элементы ниже слова ТОР.
Покажем на примере, как стековая память
помогает нам легко определить, является ли такая последовательность как g={[
]({[( )]}{ })}, правильно построенной. Элементы g будем
обозначать х1, х2,… , хn,
где xi есть одна из скобок {,
} , ( , ), [ или ]. Элементы {, ( и [ назовем ЛЕВЫМИ символами ;
скажем, что xi - левый партнер хj,
если xi=[ и хj=] , или xi=( и xj=),
или xi ={ и xj =}/
AlgorithmWELLFORMED(ПРАВИЛЬНО ПОСТРОЕННАЯ). Определяет, является ли произвольная последовательность символов xi x2...xn,,где каждый xi - одна из скобок {, }, (, ), [, или ], правильно построенной .
Шаг 0. [Инициализация ]SetTOP ←0; I←1.
Шаг 1.[ Читается последовательность слева направо]
While I≤N do through шаг 3 od/
Шаг 2.[Записывается в стек ЛЕВЫЙ символ]
Ifхi ЛЕВЫЙ символ then[ записывается xi]
else[выбирается символ из стека ]
ifTOP левый партнер хi
then выбирать элемент ТОР из памяти
elseНАПЕЧАТАТЬ « НЕПРАВИЛЬНО ПОСТРОЕННАЯ»; and STOP fifi
Шаг 3.[Прочесть следующий символ ] SetI ←I +1.
Шаг 4 . [Память пуста?] IfTOP=0 thenPRINT « ПРАВИЛЬНО ПОСТРОЕННАЯ»;
else PRINT « НЕПРАВИЛЬНО ПОСТРОЕННАЯ» FI ; andSTOP.
Применим теперь алгоритм ПРАВИЛЬНО ПОСТРОЕННАЯ к последовательности
g={ [ ] ( { [ ( ) ] } { } ) }
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.