Лабораторная работа № 1
ОПРЕДЕЛЕНИЕ ПОРЯДКА ВЫПОЛНЕНИЯ ОПЕРАЦИЙ
ПРИ ВЫЧИСЛЕНИИ АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ
Цель работы: ознакомление с польской записью арифметических выражений и стековой организацией данных, которые широко применяются в процессе трансляции языков программирования; изучение, анализ и программная реализация алгоритма вычисления арифметических выражений, представленных в польской записи.
1. Теоретическая часть
Арифметические выражения являются важным элементом языков программирования высокого уровня, а их трансляция входит в функции языковых процессоров. Поскольку эти выражения являются неотъемлемой частью фактически всех вычислительных программ САПР, в составе языковых процессоров необходимо иметь алгоритмы, распознающие арифметические выражения в тексте программы и вычисляющие их как можно быстрее и эффективнее.
В процессе трансляции арифметические выражения преобразуются в некоторую внутреннюю форму. Наиболее часто используется такое внутреннее представление арифметических выражений, как польская запись. Все формы внутреннего представления выражений, в том числе польская запись, содержат элементы двух видов - операторы и операнды. В простейшем случае операторы задаются знаками арифметических операций, такими как сложение "+", вычитание "-", умножение "", деление "/", возведение в степень "^" и т.п. Операндами являются имена переменных и константы, над которыми выполняются указанные операции.
Любому арифметическому выражению можно поставить в соответствие бинарное дерево, все конечные вершины (листья) которого соответствуют операндам, а внутренние вершины и корень - операторам. Например, дерево, описывающее арифметическое выражение
(a-b)с+d/ (e^f), (1)
имеет вид, показанный на рис. 1.
Рис. 1. Бинарное дерево для выражения (a - b) с + d / (e ^ f )
Очевидно, что при представлении арифметического выражения в виде дерева не требуются скобки, так как приоритет соответствующих операций учитывается структурой дерева. Однако бинарное дерево не позволяет однозначно задать порядок выполнения некоторых промежуточных вычислений, необходимых для получения значения всего выражения. В частности, вычитание a - b можно выполнять раньше возведения в степень e ^ f , но допустимо и обратное.
1.1. Представление арифметических выражений в польской записи
Для представления арифметических и логических выражений часто используется польская запись, которая просто и однозначно указывает порядок выполнения всех операций.
Рассмотрим некоторое выражение a + b. Для него возможны три формы представления:
a + b - обычная, или инфиксная запись;
a b + - польская, или постфиксная запись;
+ a b - префиксная запись.
Наиболее удобной для использования в трансляторах является польская запись, основные свойства которой состоят в следующем.
1. Операнды в польской записи следуют в том же порядке, что и в инфиксной форме.
2. Операторы в польской записи следуют в том порядке (слева направо), в котором они должны выполняться при вычислении выражений.
3. Операторы в польской записи располагаются непосредственно за своими операндами.
4. При использовании польской записи выражений не требуются скобки.
Необходимо заметить, что такой вид записи впервые применил польский логик Я. Лукашевич.
Указанные формы записи могут быть получены посредством использования рекурсивных алгоритмов обхода дерева, соответствующего заданному выражению. Для получения префиксной формы записи дерево обходят сверху в порядке TLR:
1) корень или верхняя точка (Т) дерева;
2) обход сверху левого (L) поддерева в порядке TLR;
3) обход сверху правого (R) поддерева в порядке TLR.
При получении постфиксной формы (польской записи) дерево просматривают снизу в порядке LRT:
1) обход снизу левого (L) поддерева в порядке LRT;
2) обход снизу правого (R) поддерева в порядке LRT;
3) корень дерева (Т).
Порядок просмотра можно пояснить на примере дерева, которое соответствует выражению a + b и приведено на рис. 2. Если начать с корня или верхней точки (T) этого дерева и напечатать "+", затем перейти к левой (L) нижней вершине и напечатать "a", а далее перейти опять в корень, спуститься вправо (R) и напечатать "b", то получим обход дерева сверху в порядке TLR. Последовательность напечатанных символов +ab будет префиксной формой выражения а + b.
Обход снизу рассмотрим на примере дерева, показанного на рис. 1. Для просмотра снизу левого (L) поддерева начинают с самой левой вершины, помеченной операндом а, проходят снизу поддерево с корнем, соответствующим оператору "-", и получают запись ab-. |
Рис. 2. Варианты обхода дерева |
Затем проходят поддерево с верхней точкой "". В результате для левого поддерева получают следующий порядок прохождения вершин: ab-c. Обход снизу правого (R) поддерева начинают с самой левой вершины этого поддерева, т.е. с вершины d. Затем проходят поддерево с корнем "^". В итоге для правого поддерева получают запись def ^ /. Прохождение всего дерева снизу завершается в корневой вершине (T), помеченной оператором "+".
В результате получается последовательность операндов и операторов следующего вида:
, (2)
которая представляет собой постфиксную форму (польскую запись) исходного выражения (1).
Прохождение этого же дерева сверху в порядке TLR позволяет получить префиксную форму выражения (1):
.
Для каждой из указанных форм записи можно построить простой алгоритм, однозначно вычисляющий выражение. Однако для автоматического вычисления выражений наиболее удобной является польская запись.