Implementation

TYPE PElement=^TElement;

TElement= RECORD VElem: TVal; Next: PElement END;

TStack= PElement;

VAR Stack: TStack;

FUNCTION Empty: BOOLEAN; BEGIN Empty: =(Stack=NIL) END;

PROCEDURE Push; VAR p: PElement; BEGIN NEW(p);

p^.VElem: =xPrm; p^.Next: =Stack; Stack: =p END;

PROCEDURE Pop; VAR xStack: PElement; BEGIN IF Stack=NIL

THEN {недопустима - стек пустой} ErrStack: =-2

ELSE BEGIN xStack: =Stack^.Next; Dispose(Stack);

Stack: =xStack END END;

FUNCTION Top; BEGIN IF Stack=NIL

THEN {недопустима - стек пустой} ErrStack: =-2

ELSE Top: =Stack^.VElem END;

PROCEDURE WriteAll; VAR p: PElement; BEGIN p: =Stack;

WHILE p< > NIL DO BEGIN WriteElement(Stack^.VElem);

p: =p^.Next END END;

INITIALIZATION {Создать пустой стек} Stack: =NIL; ErrStack: =0

END.

PROGRAM\Prg3b\PROJECT1.DPR PROGRAM\C(C++)\prg3b\prg3b.dsw

Динамическая реализация динамической памяти типа «стек» устраняет основной недостаток статической реализации, но имеет свои недостатки - например, дополнительный расход памяти на представление каждого элемента стека для хранения ссылки на следующий элемент.

Отметим технологически важный момент. Мы изменили способ реализации абстрактного типа данных «стек», но сохранили интерфейс. Это позволило сохранить без изменений программу решения задачи «Преобразовать: правильную инфиксную ® постфиксную». Сохранение ранее накопленного, повторное использование - один из важнейших вопросов современной технологии программирования.

Общий недостаток вышерассмотренных обеих реализаций понятия «стек» состоит в том, что инструменты этих модулей не позволяют работать с двумя стеками одновременно. По сути, оба модуля не столько реализуют абстрактный тип данных «стек», сколько предоставляют пользователю некий (один) информационный ресурс памяти типа «стек». Для одновременной работы с двумя стеками можно конечно продублировать модуль и использовать под одним именем для одного стека, а под другим - для другого. Но очень естественным такой выход из положения назвать трудно...

Ø Вариант 3. Другой выход из вышерассмотренного затруднения - параметризовать инструменты модуля.

UNIT UStack;

INTERFACE USES UVal;

TYPE PElement=^TElement;

TElement=RECORD VElem: UVal.TVal; Next: PElement END;

TStack= PElement;

PROCEDURE MakeNull(VAR Stack: TStack){Создать пустой стек};

FUNCTION Empty(Stack: TStack): BOOLEAN{Проверить на пустоту};

PROCEDURE Push(VAR Stack: TStack;

xPrm: UVal.TVal){Добавить, положить в стек};

PROCEDURE Pop(VAR Stack: TStack)

{Удалить, вытолкнуть из стека};

FUNCTION Top(Stack: TStack): UVal.TVal{Посмотреть вершину};

IMPLEMENTATION

PROCEDURE MakeNull(VAR Stack: TStack);

BEGIN Stack: =NIL END;

FUNCTION Empty(Stack: TStack): BOOLEAN;

BEGIN Empty: =(Stack=NIL) END;

PROCEDURE Push(VAR Stack: TStack; xPrm: UVal.TVal);

VAR p: PElement;

BEGIN NEW(p); p^.VElem: =xPrm; p^.Next: =Stack;

Stack: =p END;

PROCEDURE Pop(VAR Stack: TStack); VAR xStack: PElement;

BEGIN IF Stack=NIL THEN {недопустима - стек пустой}

ELSE BEGIN xStack: =Stack^.Next; Dispose(Stack);

Stack: =xStack END END;

FUNCTION Top(Stack: TStack): UVal.TVal;

BEGIN IF Stack=NIL THEN {недопустима - стек пустой}

ELSE Top: =Stack^.VElem END;

END.

program Project1;

uses UVal in 'UVal.pas', UStack in 'UStack.pas';

VAR Vh, Vih: FILE OF CHAR; x, y: CHAR; S: TStack;

begin Assign(Vh, 'VhPrg3.TXT'); RESET(Vh);

Assign(Vih, 'VihPrg3.TXT'); REWRITE(Vih);

MakeNull(S);

WHILE NOT EOF(Vh) DO BEGIN READ(Vh, x);

CASE x OF

'(':;

'+', '-', '*', '/': UStack.Push(S, x);

')': BEGIN y: =UStack.Top(S); WRITE(Vih, y); UStack.Pop(S)

END;

ELSE {'a'..'z'} WRITE(Vih, x);

END END; CloseFile(Vh);

WHILE NOT UStack.Empty(S) DO

BEGIN y: =UStack.Top(S); WRITE(Vih, y); UStack.Pop(S)

END; CloseFile(Vih)

end. PROGRAM\PRG3C\PROJECT1.DPR

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

Но какой ценой...

§ Объявление типа TStack пришлось перенести из раздела IMPLEMENTATION, невидимого извне, в раздел INTERFACE - инструментов для внешнего использования.

§ Теперь пользователь этих инструментов, начиная от переменной типа TStack, может получить непосредственный доступ к любому компоненту «физического» представления стека и при неаккуратном программировании полностью разрушить структуру этого представления...

§ Предыдущие реализации абстрактного типа данных «стек» позволяли писать программы, независимые от способа представления стека, и препятствовали написанию программ зависящих, защищая свои инструменты.

Механизмы защиты инструментов и уровни независимости программ от способа реализации используемых инструментов - один из важнейших вопросов современной технологии программирования.

Новая реализация оказалась совершенно незащищенной от неаккуратного вмешательства в работу инструментов...

Аккуратную реализацию абстрактного типа данных «стек» можно предложить, совместно используя механизм модулей и механизм классов.