Контрольная работа: Унификация алгебраических выражений
Алгоритмом используется два стека: стек операндов и стек операций. Строка с выражением сканируется слева направо. Если очередным элементом выражения является операнд – константа или переменная, - то он безусловно заносится в стек операндов. Если очередной элемент выражения открывающая скобка, то она безусловно заносится в стек операций. Закрывающая скобка вызывает действия, задаваемые в третьей строке таблицы.
Если очередной элемент выражения операция или скобка, то действия определяются в зависимости от соотношения приоритетов данной операции и операции на вершине стека операций (таблица 1). Обозначения: Op(E) – очередная операция из выражения Е; Op(stack) – операция на вершине стека операций. Значения приоритетов и количество операндов в операциях определяются с помощью справочника операций. Соблюдаются следующие соглашения о приоритетах:
- приоритет открывающей скобки из выражения выше приоритета любой операции на вершине стека;
- приоритет любой операции из выражения выше приоритета открывающей скобки на вершине стека операций;
- приоритет любой операции на вершине стека выше приоритета закрывающей скобки из выражения.
Таблица 1 - Связь между соотношением приоритетов операций и действиями алгоритма
| Op(E) Ä Op(stack) | Описание действий |
| > | 1)Op(E) занести в стек операций; 2)перейти к следующему элементу выражения Е |
| = | 1)сформировать тройку: - операция - с вершины стека операций; - один или два операнда - с вершины стека операндов; 2)ссылку на тройку поместить на вершину стека операндов; 3)Op(E) занести в стек операций; 4)перейти к следующему элементу выражения Е |
| < | 1)сформировать тройку: - операция - с вершины стека операций; - один или два операнда - с вершины стека операндов; 2)ссылку на тройку поместить на вершину стека операндов; 3)снова провести сравнение приоритетов и выбрать действие в соответствии с таблицей. |
Если очередной символ в выражении закрывающая скобка, а на вершине стека операций открывающая скобка, то удалить открывающую скобку из стека и перейти к следующему символу в выражении.
Работа алгоритма заканчивается, если при очередном обращении стек операций оказывается пустым. На вершине стека операндов будет находиться ссылка на выражение в префиксной форме.
Действия алгоритма иллюстрируются таблицей, в которой отображаются состояния стеков и другая информация после выполнения алгоритмом очередного шага для выражения a + b + c /( m - d ) . Символ $ используется как признак конца(дна) стека или входной строки.
Таблица 2 - Состояния основных структур алгоритма
| Стек операций | Стек операндов | Символ входной строки | Соотно-шение приори-тетов | Описание |
| $ | $ | a | ||
| $ | $a | + | > | |
| $+ | $a | b | ||
| $+ | $ab | + | = | Выделение тройки: (+ a b) |
| $+ | $(+ a b) | c | ||
| $+ | $(+ a b)c | / | > | |
| $+/ | $(+ a b)c | ( | > | |
| $+/( | $(+ a b)c | m | ||
| $+/( | $(+ a b)cm | - | > | |
| $+/(- | $(+ a b)cm | d | ||
| $+/(- | $(+ a b)cmd | ) | < | Выделение тройки: (- m d) |
| $+/( | $(+ a b)c(- m d) | ) | Удаление скобки | |
| $+/ | $(+ a b)c(- m d) | $ | < | Выделение тройки: (/ c (- md)) |
| $+ | $(+ a b) (/ c (- md)) | $ | < | Выделение тройки: (+ (+ ab) (/ c (- md))) |
| $ | $(+ (+ a b)(/ c (- md))) | $ | Конец работы |
3. Определение классов для реализации алгоритма
На рисунке 4 приведена диаграмма классов для реализации алгоритма унификации, на которой показана структура вызовов операций классов. Цифры над линиями указывают возможную последовательность вызовов. В рассматриваемой реализации алгоритма предполагается, что выражение представлено в префиксной форме. Описываться будут только те структуры данных и операции, которые связаны с принципом работы алгоритма унификации.
Рисунок 4 - Диаграмма классов для алгоритма унификации
В рассматриваемом примере реализации алгоритма унификации основную структурную единицу задает класс Lisp_item. Имя класса указывает на то, что проводится аналогия с понятием символа языка LISP. Суть заключается в том, что в LISP символ может обозначать константу, переменную, список, функцию или выражение, которое можно обрабатывать. Чтобы конкретизировать, что задает экземпляр класса Lisp _ item , в его состав вводится атрибут typ . Атрибут itm будет задавать ссылку на объект (константу, переменную или тройку – выражение, состоящее из операции и двух операндов). Причем, любой из операндов может быть экземпляром класса Lisp _ item .
Таблица 3 - Назначение операций класса Lisp _ item
| Имя операции | Описание |
unifikacia(ArrayList sp, ref ArrayList SV,TextBox tbox) | Выполняет унификацию данного экземпляра Lisp_item, где sp – список продукций (подстановок); SV – формируемый список свободных переменных; tbox – компонента для вывода текстовых сообщений. |
Primen_prod(ArrayList sp, ref ArrayList SV, TextBox tbox) | Проверяет применимость к данному экземпляру класса Lisp_item продукций из заданного списка SV. Назначение остальных параметров то же, что и в предыдущем случае. |
| zamena(ArrayList SV) | Выполняет замену свободных переменных в результирующем выражении на соответствующие им фрагменты исходного выражения. SV – список свободных переменных |
Для задания продукций (подстановок), используемых для унификации выражений, применяется класс podst . В соответствии с определением продукции атрибутами класса являются left _ part и right _ part . При этом и левая, и правая части могут представлять произвольные выражения и задаются как объекты класса Lisp _ item .
Таблица 4 - Назначение операций класса podst
| Имя операции | Описание |
| primenima(Lisp_item E, ref ArrayList SV) | Определяет применимость левой части продукции к заданному выражению. Е – унифицируемое выражение; SV – формируемый список свободных переменных. |
| zamena(ArrayListSV) | Выполняет замену свободных переменных в правой части удачно примененной продукции. |
Для работы с выражением в префиксной форме предназначен класс trojka . Атрибуты этого класса предназначены для определения основных элементов и признаков выражения в префиксной форме: operation – символ операции; priority – приоритет операции; is _ func – операция является функцией; op 1 , op 2 – операнды.
Таблица 5 - Назначение операций класса trojka
| Имя операции | Описание |
primenima(Lisp_item E, ref ArrayList SV) | Определяет применимость тройки из левой части продукции к тройке заданного выражения. Е – унифицируемое выражение; SV – формируемый список свободных переменных. |
4. Операции класса Lisp _ item
4.1 Операция выполнения унификации (unifikacia )
Действия данной операции определяются схемой на рисунке 5 и складываются из следующего. Вначале проверяется применимость продукций ко всему выражению.
Если удается удачно применить какую-либо продукцию из заданного списка, то выполняется выход. В противном случае, операция унификации (unifikacia ) вызывается для каждого из операндов выражения.
4.2 Операция проверки применимости продукций( Primen _ prod )
Действия данной операции определяются схемой на рисунке 6 и складываются из следующего. Организуется цикл просмотра списка продукций.
Для очередной продукции из списка (rpod ) вызывается операция проверки применимости продукции (Primenima ). Если операция возвращает истинное значение, то вызывается операция замены свободных переменных в правой части продукции.
Если же ни одной продукции применить не удалось, то возвращается ложное значение.
4.3 Операция замены свободных переменных ( zamena )
Действия данной операции определяются схемой на рисунке 7 и складываются из следующего. Состав выполняемых действий зависит от типа обрабатываемого элемента выражения.
В случае константы никаких действий не выполняется.
В случае простой переменной выполняется ее поиск в списке свободных переменных, после чего она заменяется соответствующим фрагментом выражения. Если обрабатываемый элемент является тройкой (операция и два операнда), то данная операция замены (zamena ) свободных переменных выполняется для каждого из операндов тройки.
5. Операции класса podst
5.1 Операция проверки применимости (primenima )
Действия данной операции определяются схемой на рисунке 8 и складываются из следующего. Вначале выполняется проверка соответствия типов левой части продукции и унифицируемого выражения. При несовпадении выполняется выход с возвратом значения false . При совпадении типов дальнейшие действия определяются типом левой части продукции.
Если левая часть – константа, то выполняется сравнение значений констант из левой части продукции и заданного выражения. Результат сравнения возвращается как результат выполнения операции.