Вычисления с использованием стека
Автоматизация вычисления выражений в обратной польской нотации основана на использовании стека. Алгоритм вычисления:
Обработка входного символа
Если на вход подан операнд, он помещается на вершину стека.
Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.
Если входной набор символов обработан не полностью, перейти к шагу 1.
После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.
Обратная польская запись совершенно унифицирована — она принципиально одинаково записывает унарные, бинарные, тернарные и любые другие операции, а также обращения к функциям, что позволяет не усложнять конструкцию вычислительных устройств при расширении набора поддерживаемых операций. Это и послужило причиной использования обратной польской записи в некоторых научных и программируемых микрокалькуляторах.
Преобразование из инфиксной нотации в постфиксную
Э. Дейкстра изобрёл алгоритм для преобразования выражений из инфиксной нотации в ОПН. Как и алгоритм вычисления ОПН, алгоритм преобразования основан на стеке. В преобразовании участвуют две текстовых переменных: входная и выходная строки. В процессе преобразования используется стек, хранящий ещё не добавленные к выходной строке операторы. Преобразующая программа читает входную строку последовательно символ за символом (символ — это не обязательно буква), выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан.
|
|
|
Простой пример
Вход: 3 + 4
Добавим 3 к выходной строке (если прочитано число, то оно сразу добавляется к выходной строке).
Помещаем + (или его Идентификатор) в стек операторов.
Добавим 4 к выходной строке.
Мы прочитали всё выражение, теперь выталкиваем все оставшиеся в стеке операторы в выходную строку. В нашем примере в стеке содержится только +.
Выходная строка: 3 4 +
Алгоритм преобразования из инфексной формы записи в постфиксную
Задана строка в инфексной форме записи выражения.
Пока есть ещё символы (под символом будем понимать операнды и операции) для чтения:
Читаем очередной символ. Если символ является числом, добавить его к выходной строке. Если символ является символом функции или левой скобкой, помещаем его в стек. При этом, если символ является оператором и его приоритет меньше или равен приоритету оператора, находящегося на вершине стека выталкиваем верхние элементы стека c бо́льшим либо равным приоритетом в выходную строку, а затем помещаем оператор в стек. Если символ является закрывающейся скобкой, выталкиваем элементы из стека в выходную строку до тех пор, пока на вершине стека не окажется открывающаяся скобка. При этом открывающаяся скобка удаляется из стека, но в выходную строку не добавляется. Когда входная строка закончилась, вытолкнуть все символы из стека в выходную строку.
|
|
|
Рассмотрим пример.
Приоритеты:
• ^ высокий
• * / средний
• + - низкий
Вход: 3 + 4 * 2 / (1 - 5)^2
Читаем «3»
Добавим «3» к выходной строке
Выход: 3
Читаем «+»
Кладём «+» в стек
Выход: 3
Стек: +
Читаем «4»
Добавим «4» к выходной строке
Выход: 3 4
Стек: +
Читаем «*»
Кладём «*» в стек
Выход: 3 4
Стек: + *
Читаем «2»
Добавим «2» к выходной строке
Выход: 3 4 2
Стек: + *
Читаем «/»
Выталкиваем «*» из стека в выходную строку, кладём «/» в стек
Выход: 3 4 2 *
Стек: + /
Читаем «(»
Кладём «(» в стек
Выход: 3 4 2 *
Стек: + / (
Читаем «1»
Добавим «1» к выходной строке
Выход: 3 4 2 * 1
Стек: + / (
Читаем «-»
Кладём «-» в стек
Выход: 3 4 2 * 1
Стек: + / ( -
Читаем «5»
Добавим «5» к выходной строке
Выход: 3 4 2 * 1 5
Стек: + / ( -
|
|
|
Читаем «)»
Выталкиваем «-» из стека в выходную строку, выталкиваем «(»
Выход: 3 4 2 * 1 5 -
Стек: + /
Читаем «^»
Кладём «^» в стек
Выход: 3 4 2 * 1 5 -
Стек: + / ^
Читаем «2»
Добавим «2» к выходной строке
Выход: 3 4 2 * 1 5 - 2
Стек: + / ^
Конец выражения
Выталкиваем все элементы из стека в строку
Выход: 3 4 2 * 1 5 - 2 ^ / +
ЛЕКЦИЯ 8. НЕЛИНЕЙНЫЕ СПИСКИ
Цели и задачи лекции: ознакомиться с принципами динамической организации нелинейных разветвленных списков.
Основные рассматриваемые вопросы: нелинейные списки, слоеные списки.
Нелинейные разветвленные списки
Нелинейным разветвленным списком является список, элементами которого могут быть тоже списки. Если же один из указателей задает порядок произвольного вида, не являющийся обратным по отношению к порядку, устанавливаемому другим указателем, то такой список будет нелинейным.
В обработке нелинейный список определяется как любая последовательность атомов и списков (подсписков), где в качестве атома берется любой объект, который при обработке отличается от списка тем, что он структурно неделим.
Если мы заключим списки в круглые скобки, а элементы списков разделим запятыми, то в качестве списков можно рассматривать такие последовательности:
|
|
|
Первый список содержит четыре элемента: атом a, список (b,c,d) (содержащий в свою очередь атомы b,c,d), атом e и список (f,g), элементами которого являются атомы f и g. Второй список не содержит элементов, тем не менее нулевой список, в соответствии с нашим определением является действительным списком. Третий список состоит из одного элемента: списка (a), который в свою очередь содержит атом а.
Другой способ представления, часто используемый для иллюстрации списков, - графические схемы, аналогичен способу представления, применяемому при изображении линейных списков. Каждый элемент списка обозначается прямоугольником; стрелки или указатели показывают, являются ли прямоугольники элементами одного и того же списка или элементами подсписка. Пример такого представления дан на рис.1.
Рис.1. Схематическое представление разветвленного списка
Разветвленные списки описываются тремя характеристиками: порядком, глубиной и длиной.
Порядок. Над элементами списка задано транзитивное отношение, определяемое последовательностью, в которой элементы появляются внутри списка. В списке (x,y,z) атом x предшествует y, а y предшествует z. При этом подразумевается, что x предшествует z. Данный список не эквивалентен списку (y,z,x). При представлении списков графическими схемами порядок определяется горизонтальными стрелками. Горизонтальные стрелки истолковываются следующим образом: элемент из которого исходит стрелка,предшествует элементу, на который она указывает.
Глубина.Это максимальный уровень, приписываемый элементам внутри списка или внутри любого подсписка в списке. Уровень элемента предписывается вложенностью подсписков внутри списка, т.е.числом пар круглых скобок, окаймляющих элемент. В списке, изображенном на рис.1, элементы a и e находятся на уровне 1, в то время как оставшиеся элементы - b, c, d, f и g имеют уровень 2. Глубина входного списка равна 2. При представлении списков схемами концепции глубины и уровня облегчаются для понимания, если каждому атомарному или списковому узлу приписать некоторое число l. Значение l для элемента x, обозначаемое как l(x), является числом вертикальных стрелок, которое необходимо пройти для того, чтобы достичь данный элемент из первого элемента списка. На рис.1 l(a)=0, l(b)=1 и т.д. Глубина списка является максимальным значением уровня среди уровней всех атомов списка.
Длина - это число элементов уровня 1 в списке. Например, длина списка на рис.1 равна 3.
Типичный пример применения разветвленного списка - представление последнего алгебраического выражения в виде списка. Алгебраическое выражение можно представить в виде последовательности элементарных двухместных операций вида:
< операнд 1 > < знак операции > < операнд 2 >
Рис.2. Схема списка, представляющего алгебраическое выражение
Выражение: (a+b)*(c-(d/e))+fбудет вычисляться в следующем порядке: a+b d/e c-(d/e) (a+b)*(c-d/e) (a+b)*(c-d/e)+fПри представлении выражения в виде разветвленного списка каждая тройка "операнд-знак-операнд" представляется в виде списка, причем, в качестве операндов могут выступать как атомы - переменные или константы, так и подсписки такого же вида. Скобочное представление нашего выражения будет иметь вид:
(((a,+,b),*,(c,-,(d,/,e)),+,f)Глубина этого списка равна 4, длина - 3.
Дата добавления: 2018-05-02; просмотров: 677; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!