Инфиксная запись (нотация) – обычная форма записи математических выражений, в которой знаки операций расположены между операндами. Вычисления производят в соответствии с приоритетом операций.
Обратная польская запись (постфиксная запись, польская инверсная запись, ПОЛИЗ) – форма записи математических выражений, в которой операнды расположены перед знаками операций. Операнды в выражении при письменной записи разделяются пробелами.
· когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке из записи;
· результат операции заменяет в выражении последовательность её операндов и её знак, после чего выражение вычисляется дальше по тому же правилу;
· результатом вычисления выражения становится результат последней вычисленной операции (в примере равен 1).
Префиксная запись (польская запись) – это форма записи логических, арифметических и алгебраических выражений. Здесь оператор располагается слева от операндов.
Стек – (англ. Stack – стопка) – структура данных с методом доступа к элементам структуры LIFO (англ. Last In – First Out, «последним пришел – первым вышел»).
Добавление элемента, называемое проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху).
Удаление элемента, называемое также выталкиванием (pop), возможно также только из вершины стека, при этом второй сверху элемент становится верхним.
Целью данной лабораторной работы является изучение программного продукта, реализующего с помощью стека алгоритмы преобразования инфиксной записи исходного арифметического выражения в постфиксную запись и префиксную запись, а также вычисление значения арифметического выражения, представленного в постфиксной записи. (В общем виде преобразуемого арифметического выражения допустимо использование строчных и прописных латинских букв и числовых целых и вещественных констант, а в преобразуемом и затем вычисляемом выражении – вещественных чисел.)
Кроме того, в данной работе будет продолжено изучение новых компонентов среды Builder. Здесь будут использованы следующие интерфейсные компоненты: ImageList – список изображений, ActionList - диспетчер действий, ToolBar – инструментальная панель.
Алгоритмы
Преобразование инфиксной записи в постфиксную запись
Инфиксная запись (тип – строка) является исходной; при преобразовании каждый символ рассматривается поочередно.
1.Если символ или последовательность символов – число или переменная (операнд), то он помещается в выходную строку – постфиксную запись.
2.Если очередной символ – знак операции (+, -, *, /), или открывающая скобка, то приоритет данной операции сравнивают с приоритетом операции на вершине стека. Операции умножения и деления имеют приоритет, равный 2, операции сложения и вычитания имеют приоритет, равный 1, а открывающая скобка - равный 3. После получения символа проверяется стек.
а.Если стек пуст, или находящийся на его вершине символ имеет меньший приоритет, чем приоритет текущего символа, то текущий символ помещается в стек.
б.Если символ, находящийся на вершине стека, имеет приоритет, больший или равный приоритету текущего символа, то символы пересылают из стека в выходную строку до тех пор, пока выполняется это условие; затем переходят к пункту а.
3.Если текуший символ – открывающая скобка, то её помещают в стек.
4.Если текуший символ – закрывающая скобка, то символы из стека извлекают в выходную строку до тех пор, пока в стеке не появится открывающая скобка, которую отбрасывают. Закрывающая скобка также отбрасывается.
5.Если все символы входной строки просмотрены, а в стеке еще остаются знаки операций, то их из стека переносят в выходную строку.
Преобразование инфиксной записи в префиксную запись
1.Реверсируют исходную строку справа налево, сохраняя порядок скобок.
2.Преобразуют полученную строку в постфиксную запись.
3.Снова реверсируют строку справа налево и получают префиксную запись.
Вычисление выражений
Для вычисления выражений исходную инфиксную запись сначала преобразуют в постфиксную запись, а затем действуют по следующему алгоритму.
1.Если очередные символы входной строки – число, то его помещают в стек.
2.Если очередной символ входной строки – знак операции, то из стека извлекают два верхних числа, используют их в качестве операндов для этой операции, а результат помещают в стек.
3.Когда вся входная строка будет просмотрена, в стеке остается одно число, которое и будет результатом вычисления выражения.
Проектирование приложения.
Выбор, размещение и задание свойств компонентов.
Коды классов, функций и обработчиков событий
Сохраните модуль под именем LR_5, а проект – под именем PR_LR_5.
Достаточно полное представление об интерфейсе можно получить из рис.5.1, рис.5.2 и заголовочного файла LR_5.h (см. ниже). Отметим лишь, что для компонентов Label1,..,8 и Edit1,..,8 установлен шрифт Font = жирный, размер 10, а сконструированное меню представлено на рис.5.2.
Все функции – для работы со стеком и записями арифметических выражений, а также данные для функций поместим в класс Stack, содержание которого представлено на рис.5.3.
Для размещения класса в проекте использован модуль, не связанный с формой. Чтобы создать такой модуль, нужно выполнить команду Файл/Новый/Другое… и открывшемся окне Новые элементы на странице Новый щелкнуть на пиктограмме Модуль. Модулю дано имя f_5. В заголовочном файле этого модуля f_5.h находятся объявления структурных типов для стеков и класса, а в файле реализации модуля f_5.cpp – реализация класса (определения функций-элементов класса).
Рис.5.1 – форма по окончании проектирования
Рис.5.2 - видна структура меню Рис.5.3 - структурные типы и классы
В файле реализации LR_5.cpp модуля LR_5 разместим обработчики событий – создание формы и щелчки на разделах меню Новое, Преобразование, Преобразование и вычисление, Выход с именами соответственно FormCreate, N2Click, N3Click, N4Click, N6Click. Заметим, что обработчик FormCreate можно вызвать двойным щелчком на форме.
Подробно остановимся на использовании новых интерфейсных компонентов среды: ImageList – список изображений, ActionList - диспетчер действий, ToolBar – инструментальная панель. Эти компоненты необходимы в технологии программирования, использующей диспетчеризацию действий.
Здесь программирование начинается с составления списка действий, которые будут доступны пользователю через разделы меню, инструментальные панели, кнопки и другие элементы управления. При программировании этот список реализуется в данном случае компонентом ActionList, обеспечивающим диспетчеризацию действий. Редактор диспетчера действий ActionList позволяет сформировать список действий, написать обработчики (если их еще нет), выполняющие задуманные действия, задать основные свойства будущих интерфейсных элементов – пиктограммы, надписи, быстрые кнопки, тексты подсказок и т.п.
После того, как список действий создан, формируют полосы действий. Это полосы, на которых располагаются интерфейсные компоненты действий – полоса главного меню и инструментальные панели. В нашем случае – полоса главного меню уже создана. При использовании диспетчера действий ActionList полосы действий добавляют на форму в виде отдельных компонентов, создают на них инициаторы действий (разделы меню, быстрые кнопки), а затем связывают инициаторы с соответствующими действиями из списка диспетчера действий ActionList. При таком связывании свойства, заложенные в действия, автоматически передаются интерфейсным компонентам.
Интерфейсные компоненты действий обычно должны содержать поясняющие их изображения. Изображения собираются в списке изображений – компоненте ImageList. Для нестандартных действий (наш случай) изображения загружаются в ImageList пользователем. А для стандартных действий они загружаются автоматически по мере формирования списка в диспетчере действий ActionList.
Диспетчеризация действий на основе компонента ActionList
1.Перенесите на форму со страницы Стандарт компонент ActionList1. Перенесите также со страницы Win32 компонент ImageList1 и сошлитесь на него в свойстве Images компонента ActionList1.
2.Загрузите в компонент ImageList1 четыре изображения. Они загружаются в процессе проектирования с помощью редактора списков изображений. Окно редактора вызывается двойным щелчком на компоненте ImageList1 или щелчком правой кнопки мыши и выбором команды контекстного меню Редактор ImageList. В окне редактора Образы можно добавить в списки изображение (кнопка Добавить), удалить изображение из списка кнопкой Удалить, очистить весь список кнопкой Очистить. При добавлении изображения в список, которое начинается с нажатия кнопки Добавить, открывается окно открытия файлов изображений, в котором можно выбрать нужный файл. Множество изображений, размещаемых обычно на кнопках, содержится в папке …\Program Files\Common Files\Borland Shared\Images\Buttons. Следует помнить, что размер всех изображений в списке должен быть одинаковым. Как правило, это размер, используемый для пиктограмм в меню, списках, кнопках. При добавлении в список изображений для кнопок надо иметь в виду, что они часто содержат не одно, а два и более изображений. В этих случаях после выбора имени файла изображений при щелчке на кнопке Открыть задается вопрос: “Bitmap dimensions for … are greater then imagelist dimensions. Separate into … separate bitmaps?” (“Размерность изображения … больше размерности списка. Разделить на … отдельные изображения?”). Если ответить отрицательно, то все изображения уменьшатся в горизонтальном размере и лягут как одно изображение. Использовать его в дальнейшем будет невозможно. Поэтому на заданный вопрос надо ответить положительно. Тогда загружаемая битовая матрица автоматически разделится на отдельные изображения, а затем те из них, которые не нужны, удаляют. Каждое загруженное в список изображение получает индекс. Именно на эти индексы впоследствии ссылаются в соответствующих свойствах разделов меню, списков, кнопок и т.д., когда надо загрузить в них то или иное изображение. Чтобы изменить последовательность изображений в списке, перетаскивают изображение мышью на новое место. Итак, изображения добавляют из файлов clear, fontbold, tools, dooropen. Ненужные изображения в окне Образы выделяют щелчком мыши и удаляют, а когда все четыре изображения с соответствующими номерами будут находиться в окне, их загружают нажатием клавиши Ок.
3.Сделайте на компоненте ActionList1 двойной щелчок, чтобы попасть в Редактор Действий (окно Редактирование Form1->ActionList1), позволяющий вводить и упорядочивать действия. Колонка Категории: не имеет отношения к проектированию данного приложения. Щелчок правой кнопкой мыши или щелчок на маленькой кнопке со стрелкой вниз правее первой быстрой кнопки окна редактирования позволяет выбрать одну из команд: Новое действие или Новое стандартное действие. Первая из них относится к вводу нового действия любого типа. Будем пользоваться только командой Новое действие. Выберите эту команду четыре раза. В колонке Действия: появятся имена действий по умолчанию: Action1, Action2, Action3, Action4.
4.Выделите Action1. В Инспекторе Объектов указанным ниже свойствам объекта действия Action1 присвойте следующие значения: Caption – Новое, Hint – очистка, ImageIndex – 0, Name – ANew, ShortCut – Ctrl+A. Для Action2: Caption – Преобразование, Hint – преобразование, ImageIndex – 1, Name – AMod, ShortCut – Ctrl+B. Для Action3: Caption – Преобразование и вычисление, Hint – преобразование и вычисление, ImageIndex – 2, Name – ARun, ShortCut – Ctrl+C. И для Action4: Caption – Выход, Hint – выход, ImageIndex – 3, Name – AExit, ShortCut –Ctrl+D.
5.На странице событий Инспектора Объектов для каждого действия определено три события: OnExecute, OnUpdate и OnHint. Событие OnExecute возникает в момент, когда пользователь инициализировал действие, например, щелкнув на компоненте (разделе меню, кнопке), связанном с данным действием. Обработчик этого события должен содержать процедуру, реализующую данное действие. Событие OnUpdate периодически возникает в промежутках между действиями. Возникновение этих событий прекращается только во время реализации события или во время, когда пользователь ничего не делает и компьютер находится в состоянии ожидания действий. Обработчик события OnUpdate может содержать какие-то настройки, подготовку ожидаемых дальнейших действий или выполнение каких-то фоновых операций. Событие OnHint возникает в момент, когда на экране отображается ярлычок подсказки в результате того, что пользователь задержал курсор мыши над компонентом, инициализирующим событие. Наличие в объекте действия событий OnUpdate и OnHint расширяет возможности по проектированию приложения. В выпадающем списке события OnExecute содержатся значения FormCreate, N2Click, N3Click, N4Click, N6Click, т.е. имена написанных обработчиков событий – создание формы и щелчки на разделах меню Новое, Преобразование, Преобразование и вычисление, Выход. Для действия Anew примите N2Click, AMod - N3Click, ARun - N4Click, AExit - N6Click.
6.В свойство Images компонента MainMenu1 внесите ImageList1. Двойным щелчком на компоненте MainMenu1 перейдите в окно Form1-> MainMenu1 Конструктора Меню. В свойство Action разделов Новое, Преобразование, Преобразование и вычисление, Выход внесите соответственно значения Anew, AMod, ARun, AExit. Как показывает Инспектор Объектов, при этом в разделы меню переносятся свойства соответствующего объекта действия.
7.Со страницы Win32 перенесите на форму инструментальную панель - компонент ToolBar. По умолчанию он расположится вверху, поскольку его свойство Align по умолчанию равно alTop. Установите Align=alNone, чтобы можно было придать любую форму и расположить ее в любом месте. Полезно также воспользоваться свойством Constraints.
8.В свойство Hint впишите инструментальная панель, в свойство Images внесите ImageList1, в ShowHint – true. Щелкните правой кнопкой мыши на компоненте ToolBar1 и из всплывшего меню выберите команду Новая кнопка. В свойство Action кнопки внесите ANew, а в свойство ShowHint – true. Повторите эту команду еще для трех кнопок, внося в свойство Action соответственно AMod, ARun, AExit, в свойство ShowHint – true. Отметим, что свойства и обработчики событий объекта действия будут перенесены на соответствующие кнопки инструментальной панели.
Тестирование и использование приложения
1.Запустите приложение на выполнение, нажав быстрые кнопки Сохранить все и Запуск.
2.Составьте тесты, которые проверят правильность сообщений об ошибках.
3.Выполните преобразования для исходного выражения в общем виде, содержащего не менее трех вложенных скобок и все арифметические операции. Вычислите значение подобного по сложности арифметического выражения.
4.Выделите в отдельный класс функции работы со стеком. Затем выполните отладку отредактированного приложения и получите результаты, представленные на рис.5.4 и 5.5.
Рис.5.4 – форма после пребразований выражения
Рис.5.5 – форма после пребразований и вычисления выражения
Контрольные вопросы
1.Внесите комментарии в файл LR_5.cpp.
2.Внесите комментарии в функции работы со стеком в файле f_5.cpp.
3.Внесите комментарии в функцию проверки исходного выражения.
4.Внесите комментарии в функцию расстановки пробелов в исходном выражении.
5.Внесите комментарии в функцию получения постфиксной записи исходного выражения с пробелами.
6.Внесите комментарии в функцию реверсирования исходного выражения с пробелами.
7.Внесите комментарии в функцию преобразования реверсированного исходного выражения с пробелами в постфиксную запись.
8.Внесите комментарии в функцию реверсирования постфиксной записи реверсированного исходного выражения с пробелами, или в функцию получения префиксной записи.
9.Внесите комментарии в функцию вычисления значения исходного выражения по постфиксной записи.
10.Где и как создается и разрушается объект класса Stack?
11.Как выделить функции работы со стеком в отдельный класс?
12.Каков список действий, доступных пользователю через разделы меню и кнопки инструментальной панели, в данной работе?