соответствует следующей последовательности действий: вызвать функцию rlineto с аргументами 144 и О, затем вызвать функцию rotate с аргументом 60, затем вызвать функцию rlineto с аргументами 144 и О и т.д. В программе PostScript, показанной на рис. 4.3, определяется и используется функция hill. Функции в языке PostScript подобны макросам: последовательность /hill { А } def делает имя hill эквивалентным последовательности операций внутри фигурных скобок. Рисунок 4.3 представляет пример программы PostScript, в которой определяется функция и вычерчивается простая диаграмма.

В данном контексте наш интерес к языку PostScript объясняется тем, что этот широко используемый язык программирования базируется на абстракции стека магазинного типа. Действительно, в аппаратных средствах многих компьютеров реализованы основные стековые операции, поскольку они являются естественным воплощением механизма вызова функций: при входе в процедуру текущее состояние программной среды сохраняется путем занесения информации в стек; при выходе из процедуры состояние программной среды восстанавливается за счет извлечения информации из стека. Как будет показано в главе 5, эта связь между магазинными стеками и программами, которые организованы в виде функций, обращающихся к другим функциям, отражает важную модель вычислительного процесса.

Возвращаясь к первоначальной задаче, отметим, что, как иллюстрирует рис. 4.4, магазинный стек можно также использовать для преобразования инфиксного арифметического выражения с круглыми скобками в постфиксную форму. При выполнении этого преобразования знаки операций заносятся в стек, а сами операнды просто передаются в выходной поток профаммы. Правая скобка показывает, что два последних числа на выходе программы являются аргументами операции, знак которой занесен в стек последним. Поэтому этот знак операции можно извлечь из стека и также передать в выходной поток программы.

Программа 4.6 представляет собой реализацию этого процесса. Обратите внимание, что аргумен-

АШ -С

dup О rlineto 60 rotate dup О rlineto -120 rotate dup 0 rlineto 60 rotate dup 0 rlineto pop }def

0 0 moveto

144 hill

0 72 moveto

72 hill

stroke

РИСУНОК 4.3 ПРОСТАЯ ПРОГРАММА НА ЯЗЫКЕ POSTSCRIPT

Диаграмма в верхней части рисунка была вычерчена программой PostScript, расположенной под ней. Программа является постфиксным выражением, в котором используются встроенные функции moveto, rlineto, rotate, stroke и dup; в ней также используется определяемая пользователем функция hill (см. текст). Графические команды являются инструкциями графопостроителю: команда moveto устанавливает печатающую головку устройства на заданную позицию страницы (координаты даются в пунктах, равных 1/72 дюйма); команда rlineto перемещает печатающую головку на новую позицию, координаты которой задаются относительно текущей позиции, и тем самым она добавляет очередной участок к пройденному пути; команда rotate изменяет направление движения печатающей головки, заставляя ее повернуть влево на заданное число градусов; команда stroke чертит пройденный путь.

ты в постфиксном выражении расположены в том же самом порядке, что и в инфиксном выражении. Забавно также отметить, что левые скобки в инфиксном выражении не нужны. Однако они необходимы, если существуют операции, имеющие разное количество операндов (см. упражнение 4.14).

Помимо того, что алгоритм, разработанный в данном разделе для вычисления инфиксных выражений, предоставил два разных примера использования абстракции стека, он и сам по себе является упражнением по абстракциям. Во-первых, входные данные преобразуются в промежуточное представление (постфиксное выражение). Во-вторых, для интерпретации и вычисления этого выражения имитируется работа абстрактной машины, функционирующей на основе стека. В целях эффективности и мобильности эта же схема работы наследуется многими современными компиляторами: задача компиляции программы на С++ для некоторого компьютера разбивается на две задачи, которые концентрируются вокруг промежуточного представления. Поэтому задача трансляции программы отделяется от задачи выполнения этой программы, точно так же как это делалось в данном разделе. В разделе 5.7 будет показано родственное, но другое промежуточное представление.

Программа 4.6 Преобразование из инфиксной формы в постфиксную

Эта программа является еще одним примером программы-клиента для стека магазинного типа. В данном случае стек содержит символы. Для преобразования (А+В) в постфиксную форму АВ+ левая скобка игнорируется, в выходной поток записывается А, в стеке запоминается знак +, в выходной поток записывается В и затем при встрече правой скобки из стека извлекается знак + и он же записывается в выходной поток.

#include <iostream.h> #include <string.h> #include STACK.cxx int main(int argc, char *argv[]) { char *a = argv[l] ; int N = strlen(a); STACK<char> ops(N); for (int i = 0; i < N; i++) {

if (a[i] == ))

cout ops. pop о ; if ((a[i] == + ) II (a[i] == *))

ops.push(a[i]); if ((a[i] >= 0) && (a[i] <= 9))

cout a[i] ;

cout endl ;

( ( ( 9 + 8 )

6 ) ) + 7 ) )

РИСУНОК 4.4

ПРЕОБРАЗОВАНИЕ

ИНФИКСНОГО

ВЫРАЖЕНИЯ В

ПОСТФИКСНОЕ

Данная

последовательность операций демонстрирует использование стека для преобразования инфиксного выражения

(5*(((9+8)*(4*6))+7)) в

его постфиксную форму S 98 + 46**7+*. Выражение обрабатывается слева направо: если встречается число, оно записывается в выходной поток; если встречается левая скобка, она игнорируется; если встречается знак операции, он заносится в стек; и если встречается правая скобка, то в выходной поток записывается знак операции, находящийся на верхушке стека.

Это приложение также иллюстрирует достоинства абстрактных типов данных и шаблонов С++. Здесь используются два разных стека, один из которых содержит объекты типа char (знаки операций), а другой - объекты типа int (операнды). С помощью АТД в виде шаблонного класса, определенного в программе 4.4, можно даже объединить две рассмотренных клиентских профаммы в одну (см. упр. 4.19). Несмотря на привлекательность решения, стоит сознавать, что это, по-видимому, не самый лучший выбор, поскольку различные реализации могут отличаться своей производительностью и, возможно, не следовало бы априори решать, что в обоих случаях будет применяться одна и та же реализация. Действительно, главное внимание уделяется реализации и производительности, и сейчас мы приступим к рассмофению этих тем применительно к стеку магазинного типа.

Упражнения

> 4.12 Преобразуйте в постфиксное выражение

(5*((9*8) + (7*(4 + 6)))).

> 4.13 Таким же способом, как на рис. 4.2, покажите содержимое стека при вычислении программой 4.5 следующего выражения

59*8746 + *213* + * + * .

> 4.14 Расширьте программы 4.5 и 4.6 таким образом, чтобы они включали операции - (вычитание) и / (деление).

4.15 Расширьте решение упражнения4.14 таким образом, чтобы оно включало унарные операции - (офицание) и $ (извлечение квадратного корня). Кроме того, измените механизм абстрактного стека в профамме 4.5 так, чтобы можно было использовать числа с плавающей точкой. Например, имея в качестве исходного выражение

{-(-1) + $((-1) * (-1)-(4 * (-1)))) / 2 программа должна выдать число 1.618034.

4.16 Напишите на языке PostScript профамму, которая чертит следующую фигуру:

4.17 Методом индукции докажите, что профамма 4.5 правильно вычисляет любое постфиксное выражение.

о 4.18 Напишите программу, которая с использованием стека магазинного типа преобразует постфиксное выражение в инфиксное.

о 4.19 Объедините программы 4.5 и 4.6 в один модуль, в котором будут использоваться два разных АТД: стек целых чисел и стек операций (знаков операций).

4.20 Реализуйте компилятор и интерпретатор для языка профаммирования, в котором каждая программа состоит из одного арифметического выражения. Выражению предшествует ряд операторов присваивания с арифметическими выражениями, состоящими из целых чисел и переменных, обозначаемых одиночными символами нижнего регистра. Например, получив входные данные

(х = 1)

(у = (X + 1))

(((X + у) * 3) + (4 * X))

программа должна вывести число 13.