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

4.3 Примеры программ-клиентов, использующих ATD стека

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

5*(((9 + 8)*(4*б))+7)

Это вычисление включает сохранение промежуточных результатов: например, если сначала вычисляется 9 + 8, придется сохранить результат 17 на время, пока, скажем, вычисляется 4*6. Стек магазинного типа представляет собой идеальный механизм для сохранения промежуточных результатов таких вычислений.

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

598 + 46**7 + *

Форма записи, обратная постфиксной, называется префиксной или Польской записью (так как ее придумал польский логик Лукашевич (Lukasiewicz)). При инфиксной Записи чтобы отличить, например, выражение

5*(((9 + 8)*(4*б))+7)

от выражения

((5*9)+8)*((4*б)+7)

требуются скобки; но при постфиксной (или префиксной) записи скобки не нужны. Чтобы увидеть почему, можно рассмотреть следующий процесс преобразования постфиксного выражения в инфиксное: все группы из двух операндов и следующим за ними знаком операции замещаются их инфиксными эквивалентами и заключаются в круглые скобки для демонстрации того, что этот результат может рассматриваться как операнд. То есть, группы аЬ* и аЬ+ замещаются группами (а * Ь) и (а + Ь), соответственно. Затем то же самое преобразование выполняется с полученным выражением, продолжая процесс до тех пор, пока не будут обработаны все операции. В нашем примере преобразование будет происходить следующим образом:

9 ( ( ( 5

8 + 9 (

) 8 + (

) 6 4

) )

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

С другой стороны, с помощью стека можно действительно выполнить эти операции и вычислить значение любого постфиксного выражения (см. рис. 4.2). Перемещаясь слева направо, мы интерпретируем каждый операнд как команду занести операнд в стек , а каждый знак операции - как команды извлечь из стека два операнда, выполнить операцию и занести результат в стек . Программа 4.5 является реализацией этого процесса на языке С++. Обратите внимание, что, поскольку АТД Стек создан на основе шаблона, один и тот же код может использоваться и для создания стека целых чисел в этой программе, и стека символов в программе 4.6.

Программа 4.5 Вычисление поафиксного выражения

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

РИСУНОК 4.2 ВЫЧИСЛЕНИЕ

ПОСТФИКСНОГО

ВЫРАЖЕНИЯ

Эта последовательность операций показывает, как стек используется для вычисления постфиксного выражения 598 + 46 **7 + *. Выражение обрабатывается слева направо и, если встречается число, оно заносится в стек; если же встречается знак операции, то эта операция выполняется над двумя верхними числами стека и результат опять заносится в стек.

Когда встречаются операнды, они заносятся в стек; когда встречаются знаки операций, из стека извлекаются два верхних элемента, над ними выполняется данная операция и результат снова заносится в стек. Порядок, в котором две операции рор() выполняются в выражениях данного кода, в языке С++ не определен, поэтому код для некоммутативных операций, таких как вычитание или деление, был бы более сложным.

В программе неявно предполагается, что целые числа и знаки операций ограничены какими-нибудь другими символами (скажем, пробелами), но программа не проверяет корректность входных данных. Последний оператор if и цикл while выполняют вычисление, подобное тому, что выполняет функция atoi языка С++, которая преобразует строки в коде ASCII в целые числа, готовые для вычислений. Когда встречается новая цифра, накопленный результат умножается на 10 и к нему прибавляется эта цифра.

#include <lo8treaffi.b> #include <8tring.b> finclude STACK.схх int main(int argc, char *argv[]) { char *a = argvtl] ; int N = strlen (a) ; STACK<int> save(N); for (int i = 0; i < N; i++) {

if (ati] == +)

save,push(save.pop() + save.pop()); if (a[i] == * )

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

save.push(0); while ((ati] >= 0) && (a[i] <= 9))

save.push(10*save.pop() + (a [1++]-0));

cout save.pop0 endl;

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

Примером такого языка является язык PostScript. Это завершенный язык программирования, в котором программы пишутся в постфиксном виде и интерпретируются с помощью внутреннего стека, точно как в программе 4.5. Хотя мы не можем осветить здесь все аспекты этого языка {см. раздел ссылок), он достаточно прост и мы можем изучить некоторые реальные программы, чтобы оценить полезность постфиксной записи и абстракции стека магазинного типа. Например, строка

5 9 8 add 4 6 mul mul 7 add mul

является программой на языке PostScript! Програмга на языке PostScript состоит из операций (таких, как add и mul) и операндов (таких, как целые числа). Программу на этом языке мы интерпретируем так же, как делали это в программе 4.5 - читая ее слева направо. Если встречается операнд, он заносится в стек; если встречается знак операции, из стека извлекаются операнды для этой операции (если они есть), а затем результат (если он есть) заносится в стек. Таким образом, на рис. 4.2 полностью описан процесс выполнения этой программы: после выполнения программы в стеке остается число 2075.

В языке PostScript имеется несколько простых функций, которые служат инструкциями для абстрактного графопостроителя; кроме того, можно определять и собственные функции. Эти функции с аргументами, расположенными в стеке, вызываются таким же способом, как и любые дру1ие функции. Например, следующий код на языке PostScript

о о moveto 144 hill О 72 moveto 72 hill stroke

соответствует последовательности действий вызвать функцию moveto с аргументами О и О, затем вызвать функцию hill с аргументом 144 и т.д. Некоторые операции относятся непосредственно к самому стеку. Например, операция dup дублирует элемент в верхушке стека; поэтому, например, код

144 dup О rlineto 60 rotate dup О rlineto