Лабораторная работа № 6
Системное программирование
Обработка арифметических и
логических выражений
Тема арифметических и логических выражений проходит через
большую часть программирования, так как с ней связаны синтаксис и семантика
языков программирования, компиляция, формальные
языки, структуры данных, логика, рекурсия и вычислительная сложность. Поскольку
эти выражения являются неотъемлемой частью фактически всех вычислительных
программ, нужно иметь алгоритмы, распознающие и вычисляющие их как можно
быстрее и эффективнее. Задача чтения произвольной последовательности S=S(1), S(2), . . ., S(N), состоящей из символов, и принятия решения о
том, что она представляет собой правильное арифметическое или логическое
выражение, является нетривиальной. Ее решение затрагивает теорию формальных
языков и составляет отдельную часть теории компиляции. Здесь у нас недостаточно
места для построения теории, необходимой, чтобы объяснить алгоритмы
распознавания выражений. Поэтому мы предположим, что все выражения правильны, и
сосредоточим усилия на более легкой задаче вычисления этих выражений.
Существует по крайней мере три различных способа определения
арифметических выражений. Учебники программирования для начинающих, как
правило, дают их на примерах. Разумная основа этого подхода заключается в том,
что можно научиться писать правильные выражения, просмотрев достаточное
количество примеров. Это в значительной степени
похоже на обучение разговорной речи на каком-нибудь языке. Так как было
замечено, что большинство программистов используют в своих программах довольно
простые выражения, этот подход в большинстве случаев представляется пригодным.
Более формальный подход заключается в том, чтобы определить
синтаксис и семантику арифметических и логических выражений с помощью контекстно-свободных
правил преобразования, как это сделано в описании многих языков
программирования. Промежуточный подход, сохраняющий некоторую долю
математической точности определений большинства языков программирования и в
значительной степени рассчитанный на интуицию, заключается в определении этих
выражений индуктивно или рекурсивно.
Арифметическое выражение, сокращенно
(а. в.), индуктивно определяется следующим образом:
1. Любая переменная — это (а. в.).
2. Любая константа — это (а. в.).
3. Любая ссылка на арифметическую
функцию — это (а. в.).
4. Если Х
— (а. в.), то (X) — тоже (а. в.).
5. Если Х и Y—оба (а.
в.), то (а. в.) также
будут (X+Y), {X-Y), (X*Y), (X/Y), (X**Y).
6. Ни один объект не является
арифметическим выражением, если то, что он арифметическое выражение, не следует
из конечного числа применений правил 1—5.
Это определение дает набор эффективных правил, пригодных для
построения любого арифметического выражения в терминах переменных, констант,
ссылок на функции и операций +, —, *, / и **. Заметим, что в этом определении отсутствуют
определения “переменной”, “константы” и “ссылки на функцию”. Рассмотрим
выражение
((( A - В) * С
)+(D / ( Е**F )))
Если это правильное арифметическое выражение, то должна
существовать возможность построить его с помощью правил 1—5. Пример такого
построения приведен на рис. 1.
Рис. 1. Построение арифметического
выражения.
Возможно иное описание этого арифметического выражения с
помощью корневого двоичного дерева — рис. 2. Заметим, что все конечные вершины
этого дерева соответствуют переменным или операндам, а все внутренние вершины
соответствуют арифметическим операциям. Если задано это двоичное дерево,
выражение легко вычисляется при известных значениях переменных. Например,
предположим, что переменные имеют следующие значения: A=4.0,
В =
1.0, С=5.0, D=64.0, E=2.0 и F=5.0.
Рис 2 Двоичное дерево для описания
арифметического выражения (((A-B)*C)+(D/(E**F)))
Рис. 3. Вычисление значения арифметического
выражения.
Значение арифметического выражения
можно вычислить, проходя вверх по дереву от конечных вершин к корню, как
показано на рис. 3.
Интересно заметить, что рис. 3, а и б наглядно
показывают, что некоторые из промежуточных вычислений, необходимых для
получения значения всего выражения, можно провести параллельно. Например,
вычитание А—В можно выполнить параллельно с возведением в степень E**F.
В литературе можно найти множество работ, посвященных параллельному вычислению
арифметических выражений.
Логические выражения можно определить так же, как и
арифметические. Для этого нам прежде всего нужно определить выражение
отношения. Выражением отношения называется выражение вида (а. в.) (отн.) (а. в.), где (отн.) — одна из следующих шести операций отношения:
< <= = ^= > >=
Логическое выражение, сокращенно (л. в.), определяется индуктивно следующим образом:
1. Любая логическая константа есть
(л. в.).
2. Любая логическая переменная есть
(л. в.).
3. Любое выражение отношения есть (л.
в.).
4. Если Х—(л. в.), то (X) — тоже (л. в.).
5. Если Х и Y— оба (л. в.), то также (л. в.) будут (X AND У), (X OR Y)
и NOT (X).
6. Ни один объект не является (л. в.), если то, что он (л. в.), не
следует из конечного числа применений правил 1—5.
Пример правильного логического
выражения
((NOT A) AND В) OR (С AND (D OR Е))
Соответствующее дерево приведено на
рис. 4.
Рис 4. Дерево для логического
выражения
Вы могли бы обратить внимание на то, что определения (а. в.)
и (л. в.) содержат, видимо, лишние скобки. Можно
дать определения, не требующие такого количества скобок, но такие определения
неизменно приводят к двусмысленностям. Например, выражения
А+В/С или NOT A AND В
должны вычисляться с использованием правила приоритета,
устанавливающего, что деление (/) имеет больший
приоритет, чем сложение (+), a NOT имеет больший
приоритет, чем AND.
С учетом этих приоритетов выражение А+В/С
эквивалентно выражению А+(В/С), a NOT A AND В
эквивалентно выражению (NOT А) AND В. Мы
ввели скобки во избежание подобных осложнений.
Интересно заметить, что три различных способа прохождения
деревьев на рис, 2 и .4 приводят к трем различным способам записи
соответствующих выражений в виде линейной последовательности символов.
Рассмотрим дерево простого
арифметического выражения (А+В),
приведенное на рис. 5.
Если мы начнем с корня или верхней точки (Т) этого дерева и напечатаем +,
затем перейдем к левой (L) нижней вершине и напечатаем А, а далее
перейдем обратно в корень и спустимся вправо (R) и напечатаем В, мы
пройдем дерево в прямом порядке.
Последовательность напечатанных символов, +АВ называется
префиксной формой
арифметического выражения; знак операции (+) предшествует
операндам А и В.
Рис 5. Три различных прохода по
двоичному дереву и соответствующие линейные выражения
Более привычная форма арифметического выражения (А+В) называется инфиксной формой; она получается при прохождении дерева в обратном
порядке, обозначаемом LTR.
Постфиксная форма
арифметического выражения — в которой знак операции следует за
операндами, например АВ+, получается при концевом
порядке (LRT) прохождения дерева.
Здесь будет поучительно рассмотреть
снова дерево на рис. 2.
Для прохождения этого дерева в прямом порядке мы начнем с
самой верхней вершины ТОР (помеченной +). Затем
пройдем в прямом порядке левое поддерево (с корнем, помеченным *) и далее правое поддерево в прямом порядке (с
корнем, помеченным /). Прохождение левого поддерева
в прямом порядке начинается с корня (помеченного *),
затем следует прямое прохождение левого его поддерева (порождающее
последовательность —АВ) и далее правого
поддерева (последовательность С). Поэтому вся последовательность, порождаемая
прохождением левого поддерева вершины ТОР, будет *—
АВС. Аналогично прохождение в прямом порядке
правого поддерева с корнем, помеченным /, порождает
последовательность /D**EF. Таким образом, прохождение всего дерева в
прямом порядке порождает последовательность
Прохождение этого дерева в обратном и
концевом порядках порождает последовательности соответственно
Заметим, что во всех трех выражениях порядок вхождения
переменных совпадает; меняется только порядок знаков операций. Заметим также,
что ни одно из этих выражений не имеет скобок, и, таким образом, если не заданы
правила приоритета, значение приведенного выше
выражения в инфиксной форме нельзя вычислить однозначно.
По причинам, которые станут очевидными, определение значения
этого выражения ни в префиксной, ни в постфиксной форме не содержит
двусмысленностей. Иначе говоря, можно для каждой из форм построить простой
алгоритм, однозначно вычисляющий выражение в этой форме. Приведем алгоритм
вычисления значения арифметического выражения в постфиксной форме.
Algorithm POSTFIX. Вычислить арифметическое выражение в
постфиксной форме; выражение состоит из последовательности S(1) S(2) . . . S(N), N>=1, где S(1)
— либо буква (т. е. операнд, или переменная),
либо один из знаков +,—,
*,/,** (т.е. двухместная арифметическая операция);
в алгоритме используется стек STORE.
Шаг 0. [Инициализация] Set J = 0.
Шаг 1. [Цикл] For I = 1 to N do шаг 2 od;
STOP. (Значение выражения будет на верху стека
STORE.)
if S(I)
— операнд then [поместить S(I) на стек]
set J= J + 1;
else [оценка подвыражения]
set
T1 = STORE(J);
[выполнение
операции S(l) над Т1 и Т2]
set T3 = T1 S(I) T2;
set J = J-1; and STORE(I)
= T3
endif.
Рис. 6 иллюстрирует выполнение алгоритма POSTFIX над
арифметическим выражением в постфиксной форме: АВ—C*DEF**/+. Например, в
строке I=5 входной символ S(5) = * вызывает перемножение значений двух самых верхних
элементов стека, С и 3.0 (строка 4); эти два элемента затем удаляются со
стека, а их произведение 15.0 помещается на верх стека.
Рис. 6. Вычисление арифметического выражения
в постфиксной форме с использованием алгоритма POSTFIX
Доказательство правильности алгоритма
POSTFIX можно получить индукцией по длине N постфиксного выражения S(1)
S(2). . . S(N). Такое
доказательство зависит от индуктивного определения арифметического выражения и
от процесса трансляции арифметического выражения из инфиксной формы в
постфиксную.
Очевидно, что алгоритм POSTFIX
работает правильно на постфиксных выражениях длины N
= 1 или N=3. (По определению не существует постфиксных
выражений длины N=2.) Это можно проверить с
помощью ручного вычисления. Поэтому предположим, что алгоритм POSTFIX правильно
вычисляет все постфиксные выражения длины <= N.
Рассмотрим произвольное постфиксное
выражение S(1) S(2)... S(N+1)
длины N+1. Пусть k —
наименьшее целое, такое, что S(k) —
операция. Тогда легко видеть, что эта операция должна быть применена к S(k—1) и S(k—2);
S(k—1) и S(k—2) — оба являются операндами. Вообще
говоря, S(I—1) и S(I—2) не обязательно операнды, если S(l) — операция.
Однако из-за того, что S(k) — первая операция в последовательности, S(k—1) и S (k— 2) должны быть операндами.
На шаге 2 алгоритм POSTFIX удаляет S(k—1) и S(k— 2) со
стека, вычисляет
T=S(k— l)
S(k) S(k—2) и помещает Т на стек, как если бы Т был еще одним
операндом.
В этот момент конфигурация стека в
точности такова, как было бы в случае, если первоначальное постфиксное
выражение было более коротким:
Но, поскольку значение такого
измененного выражения (можно показать, что оно правильное постфиксное
выражение) равно значению первоначального выражения и так как по предположению
индукции алгоритм POSTFIX правильно работает на всех постфиксных выражениях длины
<= N, мы заключаем, что алгоритм POSTFIX
правильно вычисляет исходное выражение.
Полное доказательство правильности
алгоритма POSTFIX должно было бы включать в себя доказательства некоторых из
приведенных выше утверждений. Мы опускаем эти доказательства ради краткости.
Легко видеть, что постфиксное выражение можно вычислить за время 0(N) с
помощью стека, так как при чтении каждого из N символов S(1), S(2), . ..., S(N) выполняется не более, чем постоянное число
операций. Следует отметить несколько свойств алгоритма POSTFIX:
1. Алгоритм предполагает, что входная
последовательность является правильным постфиксным выражением; отсутствуют
тесты, гарантирующие правильность входной последовательности.
2. Алгоритм разрабатывался для
обработки выражений, в которых операнды не должны состоять из нескольких букв или цифр.
3. Недопустимо появление в выражении
констант или обращений к функциям.
4. В выражении не должно быть
одноместных операций, например —А или +А—В.
5. Алгоритм никогда не инициализирует
стек нулями и не заполняет стек нулями после того, как значения были
использованы; наверное, это стоило бы делать из эстетических соображений, но не
обязательно.
Можно, однако, изменить алгоритм POSTFIX так, чтобы можно было
освободиться от каждого из этих пяти условий; мы оставляем это в качестве
упражнения вместе с задачей реализации алгоритма POSTFIX.
Мы уже убедились, насколько легко
вычисляется арифметическое выражение, как только оно переведено в постфиксную
форму. Однако в большинстве языков программирования требуется записывать
арифметические выражения в инфиксной форме. Следующий алгоритм разработан для
перевода выражений из инфиксной формы в постфиксную. Он основан на таком
правиле приоритетов:
Алгоритм работает, читая символы
инфиксного выражения слева направо. Все операнды (переменные) поступают на выход по мере чтения; остальные символы помещаются на
стек и либо удаляются, либо поступают на выход позже в соответствии с
приведенным выше правилом приоритетов.
Algorithm IТР (Инфиксная в Постфиксную). Перевести инфиксное выражение S(1) S(2)... S(N), N>=1, в постфиксную форму. S(/) — либо буква (т. е.
операнд, или переменная), левая или правая скобка, либо знак операции (т. е.
один из символов +, —,
*, /, или **. Алгоритм использует стек STORE и приоритетную
функцию Р,
где “е”, “(”,
“)” имеют приоритет 0, Р(+)=Р(-)=1, Р (*)=Р(/)=2, Р(**)=3.
Шаг 0. [Инициализация]
Set STORE (1)=е; and J = 1.
Шаг 1. [Цикл] For I
= 1 to N do through шаг 6 od.
Шаг 2. [Буква] If
S(I) буква then PRINT S(I) fi.
Шаг 3. [Левая скобка] If S(I)= “(” then [поместить на стек]
fi.
Шаг 4. [Правая скобка] If S(I)=“)” then [снять со стека]
while
STORE(J) ^= “(” do шаг 5 od;
fi.
Шаг 5. [Печать верхнего элемента
стека] PRINT STORE(J); and set J = J - 1.
Шаг 6. [Оператор] While
Р
(S(I)) <= P(STORE (J)) do PRINT STORE (I);
od;
[поместить на стек] set J
= J+1; and
STORE (J) = S(I).
Шаг 7. [Печать остатка стека] While
STORE(J) ^= e do
PRINT STORE(J);
od;
and STOP.
На рис. 7 приведена блок-схема
алгоритма IТР, а рис. 8 иллюстрирует выполнение этого алгоритма на заданном
инфиксном арифметическом выражении. Например, в строке 3 знак операции
помещается на стек; в строке 4 операнд В поступает на выход; в строке 5
символ “)” вызывает передачу на выход верхнего
символа стека (этим символом оказался знак —).
Рис. 7. Блок-схема алгоритма IТР
Сложность алгоритма IТР оказывается О(N).
Это следует из таких свойств алгоритма:
1. Один проход производится над N символами последовательности
2. На стек может попасть самое большее N/2 символов (т. е. операций).
3. Все символы, остающиеся на стеке, могут быть выведены по окончании чтения не более, чем за 0(N) операций
4. Для обработки произвольного символа в последовательности требуется не более постоянного числа операций.
Рис. 8. Преобразование выражения из инфиксной формы в постфиксную с помощью алгоритма ITP
Задание.
Реализовать алгоритмы:
А) преобразования из Инфиксной в
Постфиксную форму;
Б) вычисления выражения по
постфиксной форме в виде отдельных подпрограмм - функций.
В) Написать программу обработки и
вычисления правильного арифметического выражения с выдачей промежуточных и
окончательных результатов в виде, представленном на рис. 1 и рис. 8.
Арифметическое выражение должно
задаваться в виде символьной строки как параметр программы. Конкретные значение
переменных вводить по запросу программы.